Cho một dãy số nguyên có N phần tử. Hãy sắp xếp dãy số sao cho nữa dãy đầu tăng và nửa dãy sau giảm. Nếu dãy số có số lượng phần tử lẻ, thì phần tử chính giữa được giữ nguyên vị trí

Cho một dãy số nguyên có N phần tử.Hãy sắp xếp dãy số sao cho nữa dãy đầu tăng và nửa dãy sau giảm.
Nếu dãy số có số lượng phần tử lẻ, thì phần tử chính giữa được giữ nguyên vị trí.
Dữ liệu đầu vào:
- Dòng đầu tiên là số nguyên dương cho biết số lượng phần tử trong dãy số
- Dòng tiếp theo là N số trong dãy, mỗi số cách nhau 1 khoảng trắng
Dữ liệu đầu ra:
- Dãy số được sắp xếp theo yêu cầu. Mỗi số được cách nhau 1 khoảng trắng
Vd: 
input: 
8
4 2 3 1 9 6 8 7
output: 
1 2 3 4 9 8 7 6

input:
9
4 2 3 1 5 9 6 8 7
output: 
1 2 3 4 5 9 8 7 6