CSES - Two Stacks Sorting | Sắp xếp bằng Hai Ngăn xếp

Tác giả:

Dạng bài

Ngôn ngữ cho phép

~~Assembly~~, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, ~~Swift~~

Điểm: 2100 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một dãy input gồm \(n\) số. Mỗi số nguyên từ \(1\) đến \(n\) xuất hiện đúng một lần trong dãy.

Nhiệm vụ của bạn là tạo một dãy output đã sắp xếp sử dụng hai ngăn xếp (stack). Ở mỗi bước, bạn có thể thực hiện một trong các thao tác sau:

Di chuyển số đầu tiên từ dãy input vào một stack
Di chuyển một số từ một stack đến cuối dãy output

Input

Dòng đầu tiên là một số nguyên \(n\).

Dòng thứ hai chứa \(n\) số nguyên: các số của dãy input.

Output

In ra \(n\) số nguyên: với mỗi số là stack nó được chuyển vào (\(1\) hoặc \(2\)).

Bạn có thể in ra bất kỳ đáp án hợp lệ nào. Nếu không có đáp án, in ra IMPOSSIBLE.

Giới hạn

\(1 \le n \le 2 \cdot 10^5\)

Ví dụ

Input

5
2 3 1 5 4

Output

1 2 1 1 2

Bình luận

1
vanphukhang_0604 11:37 p.m. 23 Tháng 8, 2023 ← đã chỉnh sửa →
CSES - Two Stacks Sorting | Sắp xếp bằng hai ngăn xếp

Bạn được cho một dãy input gồm \(n\) số. Mỗi số nguyên từ \(1, \ldots, n\) xuất hiện đúng một lần trong dãy.

Nhiệm vụ của bạn là tạo một dãy output đã sắp xếp sử dụng hai ngăn xếp (stack). Ở mỗi bước, bạn có thể thực hiện một trong các thao tác sau:

Di chuyển số đầu tiên từ dãy input vào một stack

Di chuyển một số từ một stack đến cuối dãy output

Input

Dòng đầu tiên chứa số nguyên \(n \ (1 \leq n \leq 2 \cdot 10^5)\).

Dòng thứ hai chứa \(n\) số nguyên: các số của dãy input.

Output

In ra \(n\) số nguyên thể hiện stack mà mỗi số trong dãy input được đưa vào. Bạn có thể in bất kì cách sắp xếp nào hợp lệ.

Nếu không có cách sắp xếp, hãy in ra IMPOSSIBLE.

Example

Test 1

Input

5 2 3 1 5 4

Output

1 2 1 1 2
1 phản hồi