Bessie biết một số \(x+0.5\), trong đó \(x\) là một số nguyên từ \(0\) đến \(N\), kể cả hai đầu mút (\(1\le N\le 2 \cdot 10^5\)).

Elsie đang cố đoán số này. Cô có thể đặt câu hỏi dạng "số \(i\) là cao hay thấp?" với một số nguyên \(i\) từ \(1\) đến \(N\), kể cả hai đầu mút. Bessie trả lời "HI" nếu \(i\) lớn hơn \(x+0.5\), hoặc "LO" nếu \(i\) nhỏ hơn \(x+0.5\).

Elsie nghĩ ra chiến lược sau để đoán số của Bessie. Trước khi đoán, cô tạo một danh sách gồm \(N\) số, trong đó mỗi số từ \(1\) đến \(N\) xuất hiện đúng một lần (nói cách khác, danh sách là một hoán vị kích thước \(N\)). Sau đó cô duyệt danh sách và lần lượt đoán các số theo thứ tự xuất hiện.

Tuy nhiên, Elsie bỏ qua mọi lượt đoán không cần thiết. Cụ thể, nếu Elsie sắp đoán số \(i\), nhưng trước đó cô đã đoán một số \(j<i\) và Bessie trả lời "HI", Elsie sẽ không đoán \(i\) mà chuyển sang số tiếp theo trong danh sách. Tương tự, nếu cô sắp đoán số \(i\), nhưng trước đó đã đoán một số \(j>i\) và Bessie trả lời "LO", Elsie sẽ không đoán \(i\) mà chuyển sang số tiếp theo. Có thể chứng minh rằng với chiến lược này, Elsie luôn xác định duy nhất được \(x\), bất kể hoán vị cô tạo ra là gì.

Nếu ghép nối tất cả các câu trả lời "HI" hoặc "LO" của Bessie thành một xâu duy nhất \(S\), thì số lần Bessie nói "HILO" là số xâu con độ dài \(4\) của \(S\) bằng "HILO".

Bessie biết Elsie sẽ sử dụng chiến lược này; hơn nữa, cô cũng biết chính xác hoán vị Elsie sẽ dùng. Tuy nhiên, Bessie chưa quyết định chọn giá trị \(x\) nào.

Hãy giúp Bessie xác định số lần cô sẽ nói "HILO" ứng với mỗi giá trị \(x\).

Dữ liệu vào

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

Dòng thứ hai chứa hoán vị kích thước \(N\) của Elsie.

Dữ liệu ra

Với mỗi \(x\) từ \(0\) đến \(N\), kể cả hai đầu mút, in trên một dòng mới số lần Bessie sẽ nói HILO.

Phân nhóm

• Dữ liệu 1–4: \(N \leq 5000\).
• Dữ liệu 5–8: Hoán vị được chọn ngẫu nhiên đều.
• Dữ liệu 9–20: Không có ràng buộc bổ sung.

Ví dụ

5
5 1 2 4 3

0
1
1
2
1
0

Nguồn

USACO 2021 December Contest, Gold — HILO. Tác giả: Richard Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1162