Bấm phím đàn piano

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một dãy nốt nhạc $a_{1}, a_{2}, \dots, a_{n}$ , trong đó $a_{i}$ là vị trí của nốt thứ $i$ trên bàn phím piano (số càng lớn thì nốt càng nằm về phía bên phải).

Bạn cần gán cho mỗi nốt một ngón tay $b_{i} \in {1, 2, 3, 4, 5}$ để chơi nốt đó. Cách gán ngón được gọi là hợp lệ nếu với mọi $1 \leq i \leq n - 1$ :

Nếu $a_{i} < a_{i + 1}$ thì $b_{i} < b_{i + 1}$ .
Nếu $a_{i} > a_{i + 1}$ thì $b_{i} > b_{i + 1}$ .
Nếu $a_{i} = a_{i + 1}$ thì $b_{i} \neq b_{i + 1}$ .

Hãy in ra một cách gán ngón hợp lệ bất kỳ, hoặc cho biết không tồn tại.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số lượng nốt.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

Nếu không có cách gán hợp lệ, in ra $- 1$ .
Ngược lại, in ra $n$ số nguyên $b_{1}, b_{2}, \dots, b_{n}$ (mỗi số trong ${1, 2, 3, 4, 5}$ ) cách nhau bởi dấu cách — một cách gán hợp lệ bất kỳ.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
5 1 1 4 2 2	2 1 3 2 1	Một cách hợp lệ: $2 \to 1$ (nốt bằng nhau, ngón khác nhau), $1 \to 3$ (nốt tăng, ngón tăng), $3 \to 2$ (nốt giảm, ngón giảm), $2 \to 1$ (nốt bằng nhau, ngón khác nhau). Các đáp án khác như 1 4 5 4 5 cũng được chấp nhận.
7 1 5 7 8 10 3 1	1 2 3 4 5 2 1	Nốt tăng liên tục 5 bước rồi giảm 2 bước — có nhiều cách hợp lệ; ví dụ 1 2 3 4 5 4 3 cũng được.
1 50	1	Chỉ có một nốt, dùng ngón nào cũng được.

Bình luận

Không có bình luận tại thời điểm này.