Bạn có một dãy gồm n số nguyên dương A1, A2, …, An. Nhiệm vụ của bạn là sắp xếp dãy số này theo một quy tắc sau: Nửa đầu của dãy số (tính từ trái qua phải) được sắp xếp theo thứ tự giảm dần

code c++ nhé
----- Nội dung ảnh -----
Bài 1. SORT
Tên file: SORT.CPP

Bạn có một dãy gồm n số nguyên dương A1, A2, …, An. Nhiệm vụ của bạn là sắp xếp dãy số này theo một quy tắc sau:
- Nửa đầu của dãy số (tính từ trái qua phải) được sắp xếp theo thứ tự giảm dần.
- Nửa sau của dãy số (tính từ trái qua phải) được sắp xếp theo thứ tự tăng dần.

Nếu n là lẻ, phần tử ở vị trí giữa sẽ thuộc nửa trước và sẽ nằm trong đoạn giảm dần.

INPUT: SORT.INP
- Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 10^5)
- Dòng thứ hai chứa n số nguyên dương A1, A2, …, An (1 ≤ ai ≤ 10^6)

OUTPUT: SORT.OUT
- Xuất ra một dòng duy nhất chứa dãy số đã được sắp xếp theo quy tắc trên.

Ví dụ:
SORT.INP
6
5 2 6 10 4
7 9 3

SORT.OUT
6 5 2 4 10 7
3 9