Vòng quay Ferris nổi tiếng ở quảng trường chính Cesenatico đã được tháo dỡ trong mùa đông. Mùa hè sắp đến và đã đến lúc lắp lại vòng quay.

Có \(N\) cabin riêng lẻ, đánh số từ \(0\) đến \(N-1\), cần được nối thành một vòng tròn. Số hiệu cabin không nhất thiết trùng với thứ tự lắp đặt. Mỗi cabin có một khớp nối với cabin kế tiếp theo chiều kim đồng hồ, thuộc một trong hai loại:

• +: chỉ có thể nối với cabin có số hiệu lớn hơn;
• -: chỉ có thể nối với cabin có số hiệu nhỏ hơn.

Hình 1: \(N=5\) cabin rời, mỗi cabin có một khớp loại + hoặc -.

Hãy xác định có thể lắp tất cả \(N\) cabin thành một vòng quay hay không. Nếu có, hãy tìm một thứ tự hợp lệ.

Hình 2: Một vòng quay Ferris hợp lệ được lắp từ năm cabin ở Hình 1.

Một thứ tự hợp lệ là dãy \(C_0,C_1,\ldots,C_{N-1}\) thỏa mãn:

• Mỗi số từ \(0\) đến \(N-1\) xuất hiện đúng một lần.
• Với mọi \(0\le i\le N-2\): nếu cabin \(C_i\) có loại + thì \(C_{i+1}>C_i\); nếu có loại - thì \(C_{i+1}<C_i\).
• Cabin \(C_0\) cũng phải thỏa điều kiện do loại khớp của cabin \(C_{N-1}\) đặt ra.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\).

Dòng thứ hai chứa xâu \(S\) độ dài \(N\), chỉ gồm + và -. Ký tự \(S_i\) là loại khớp của cabin \(i\).

Dữ liệu ra

Nếu không tồn tại thứ tự hợp lệ, in NO.

Nếu tồn tại, in YES, sau đó in một dòng gồm \(N\) số nguyên là các số hiệu cabin theo chiều kim đồng hồ, bắt đầu tại vị trí bất kỳ. Có thể in bất kỳ đáp án hợp lệ nào.

Ràng buộc

• \(3\le N\le300\,000\).
• \(S_i\) là + hoặc -.

Phân nhóm

1. \(16\) điểm: \(N=3\).
2. \(13\) điểm: xâu \(S\) có đúng một ký tự +.
3. \(24\) điểm: các ký tự + và - xen kẽ, tức \(S_i\ne S_{i+1}\) với mọi \(0\le i\le N-2\).
4. \(23\) điểm: \(N\le1000\).
5. \(24\) điểm: không có ràng buộc thêm.

Ví dụ

3
+++

NO

5
+-+--

YES
0 3 2 4 1

7
------+

NO

8
+-+-+-+-

YES
3 2 4 6 7 1 0 5

11
+++--+-++--

YES
10 0 5 8 9 4 2 6 3 1 7

Nguồn

EGOI 2026 - Ngày 1, Ferris Wheel.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).