Seta đang tạo các bài toán cho CCO! Cô ấy đã nghĩ ra bài toán sau:

Cho một mảng $A[1, \dots, N]$ với các giá trị nằm trong phạm vi $[1, N]$, định nghĩa $B[i]$ là số lượng các cặp $(\ell, r)$ sao cho $\ell \leq i \leq r$ và $$A[i] = \min(A[\ell], A[\ell+1], \dots, A[r-1], A[r]).$$

Hãy in ra mảng $B[1, \dots, N]$.

Tuy nhiên, vào ngày trước khi CCO diễn ra, máy tính của Seta bị hỏng và cô ấy chỉ có thể khôi phục được các tệp đầu ra. Với mảng đầu ra $B[1, \dots, N]$ đã cho, bạn có thể viết một chương trình để khôi phục mảng đầu vào $A[1, \dots, N]$ không?

Seta nhắc bạn rằng mảng $A$ không nhất thiết phải là duy nhất, và cô ấy sẽ chấp nhận bất kỳ mảng hợp lệ nào.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $N$. Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách $B[1], \dots, B[N]$ ($1 \leq B[i] \leq N^2$).

Bảng sau đây cho biết cách phân bổ 25 điểm có sẵn:

Dữ liệu ra

Xuất ra $N$ số nguyên cách nhau bởi dấu cách, mảng $A[1], \dots, A[N]$, trong đó $1 \leq A[i] \leq N$. Đảm bảo rằng luôn tồn tại ít nhất một mảng $A$ hợp lệ.

Nếu có nhiều hơn một mảng hợp lệ, bạn có thể xuất ra bất kỳ mảng hợp lệ nào. Đặc biệt, ngay cả khi mảng $A$ ban đầu là một hoán vị, câu trả lời của bạn không bắt buộc phải là một hoán vị.

Ví dụ

Dữ liệu vào 1

3
3 1 2

Dữ liệu ra 1

1 3 2

Ghi chú 1

• Các mảng con $[1, 3, 2], [1, 3], [1]$ có giá trị nhỏ nhất là $1$. Có $3$ mảng con như vậy.
• Mảng con $[3]$ có giá trị nhỏ nhất là $3$. Có $1$ mảng con như vậy.
• Các mảng con $[3, 2]$ và $[2]$ có giá trị nhỏ nhất là $2$. Có $2$ mảng con như vậy.

Dữ liệu vào 2

2
2 2

Dữ liệu ra 2

1 1

Dữ liệu vào 3

3
1 4 1

Dữ liệu ra 3

2 1 3

Ghi chú 3

Lưu ý rằng $A = [2, 1, 2]$ cũng sẽ được giám khảo chấp nhận.