Ổn định số âm trước số không âm

Bối cảnh

Một bộ dữ liệu cần đưa tất cả số âm lên trước, sau đó là các số không âm, nhưng phải giữ nguyên thứ tự tương đối trong mỗi nhóm.

Không dùng stable_partition hay vector; hãy xây mảng phụ bằng hai lượt duyệt.

Yêu cầu

1. Đọc n và mảng.
2. Lượt 1 ghi các phần tử âm vào mảng phụ theo thứ tự cũ.
3. Lượt 2 ghi các phần tử không âm.
4. In mảng kết quả.

Input

Dòng 1: n. Dòng 2: n số.

Output

Một dòng kết quả.

Ràng buộc

1 ≤ n ≤ 5000.

Ví dụ 1

Input

6
1 -1 2 -2 0 -3

Output

-1 -2 -3 1 2 0

Giải thích

Các số âm theo thứ tự là -1,-2,-3. Các số không âm theo thứ tự là 1,2,0. Kết quả -1 -2 -3 1 2 0.

Ví dụ 2

Input

4
-1 -2 -3 -4

Output

-1 -2 -3 -4

Giải thích

Toàn bộ dãy đã là số âm nên thứ tự không thay đổi.

Thông tin học tập

• Module: M03
• Buổi: B10
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: static arrays, stable partition, auxiliary array, multi-pass traversal
• Giới hạn kiến thức: B01-B10
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100