Nam có n viên gạch được đánh số từ 1 đến n. Các viên gạch có độ cứng lần lượt là a1, a2,..., an. Một viên gạch có độ cứng x nghĩa là Nam có thể chồng lên trên viên gạch đó tối đa x viên gạch khác, nếu chồng nhiều hơn thì viên gạch đó bị vỡ. Hỏi Nam có thể sắp được chồng gạch cao nhất là bao nhiêu?

Đầu vào:

Dòng đầu tiên là số nguyên n - là số viên gạch.

Dòng tiếp theo gồm n số nguyên a1, a2,.... an mỗi số cách nhau một khoảng trắng.

Ràng buộc: 1<=n<=10^5; 0 <= ai <= 10^6

Input:

4
1 2 3 4

Output:

4

Tèo và Tý vào Trung tâm thương mại để mua đồ. Khi vào siêu thị, 2 bạn thấy một thang cuốn và ở các bậc thang được đánh số thứ tự từ 1 đền n, trên mỗi bậc thang có ghi một số nguyên dương. Tuy nhiên, do thang cuốn liên tục lặp lại nên các bậc thang cũng lặp lại theo đúng trật tự. Tý đố Tèo tính tổng của m bậc thang liên tiếp bắt đầu từ bậc thang thứ k, nếu Tèo tính đúng sẽ được Tý mua cho một món quà trong Trung tâm thương mại.

Hãy giúp Tèo tính toán tổng này để nhận được quà từ Tý.

Yêu cầu: Nhập vào từ bàn phím

• Dòng thứ nhất chứa các số nguyên dương n, m, k cách nhau bởi dấu cách (~m, k ≤ 10^8; n ≤ 10^6~)

• Và dòng thứ 2 chứa n số nguyên dương ai, a2, a3, ..., an cách nhau bởi dấu cách là các số ghi trên các bậc thang từ bậc thứ nhất đến bậc thứ n của thang cuốn. (~1 ≤ ai ≤ 10^9~)

Kết quả: In ra màn hình số nguyên dương duy nhất là kết quả bài toán chia lấy dư cho ~10^9+ 7~

Input:

6 8 3
3 4 2 1 4 5

Output:

22

Giải thích: 8 số nguyên liên tiếp bắt đầu từ vị trí số 3 là: 2 1 4 5 3 4 2 1

Kết quả: (2 + 1 + 4 + 5 + 3 + 4 + 2 + 1) mod 1000000007 = 22

Cho mảng A[] gồm N số, hãy thực hiện các thao tác theo nguyên tắc dưới đây:

1. Ta chọn một mảng con sao cho phần tử ở giữa của mảng con cũng là phần tử ở giữa của mảng A[] (trong trường hợp N lẻ).

2. Đảo ngược mảng con đã chọn trong mảng A[]. Ta được phép chọn mảng con và phép đảo ngược mảng con bao nhiêu lần tùy ý.

Ví dụ với mảng A[] = (1, 6, 3, 4, 5, 2, 7} ta có câu trả lời là YES vì: ta chọn mảng con {3, 4, 5) và đảo ngược để nhận được mảng All=(1, 6, 5, 4, 3, 2, 7}, chọn tiếp mảng con {6, 5, 4, 3, 2} và đảo ngược ta nhận được mảng A[]=(1, 2, 3, 4, 5, 6, 7}.

Hãy cho biết ta có thể sắp xếp được mảng A[] bằng cách thực hiện các thao tác kể trên hay không?

Đầu vào:

Dòng 1 chứa số nguyên dương N là số lẻ.

Dòng 2 chứa N số nguyên của mảng A[]

Ràng buộc: 1 <= N <= 10^6; 0 <= A[i] <= 10^9

Đầu ra: In ra YES hoặc NO là đáp án của bài toán

Input 01:

5
1 4 3 2 5

Output 01:

YES

Input 02:

5
1 3 8 7 3

Output 02:

NO