Trường JOIG có \(N\) lớp, được đánh số từ \(1\) đến \(N\). Ngay trước nội dung cuối của hội thao, lớp \(i\) có \(A_i\) điểm. Ở nội dung cuối, tất cả \(N\) lớp đều tham gia và nhận các hạng khác nhau từ \(1\) đến \(N\). Lớp đứng hạng \(j\) được cộng \(N-j+1\) điểm.

Sau đó, hạng chung cuộc được xác định theo điểm giảm dần; nếu bằng điểm thì lớp có số nhỏ hơn đứng trước. Với mọi kết quả có thể có của nội dung cuối, hãy tính số lượng hạng chung cuộc khác nhau mà mỗi lớp có thể đạt được.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In \(N\) số nguyên trên một dòng, cách nhau bởi dấu cách. Số thứ \(i\) là số hạng chung cuộc khác nhau mà lớp \(i\) có thể đạt được.

Ràng buộc

• \(1\le N\le1000000\).
• \(1\le A_i\le10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(12\) điểm: \(N\le9\).
2. \(27\) điểm: \(N\le300\).
3. \(21\) điểm: \(N\le5000\).
4. \(29\) điểm: \(N\le200000\).
5. \(11\) điểm: không có ràng buộc thêm.

Ví dụ

4
5 2 3 6

3 2 3 3

3
1000000000 1 1

1 2 2

7
11 10 17 10 15 7 11

7 6 3 6 5 4 6

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 1, bài Sports Festival.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.