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

Nhập vào một mảng các số nguyên dương A có N phần tử, in ra số nguyên dương nhỏ nhất chưa xuất hiện trong mảng.

Ràng buộc: ~0 < N \leq 10^6~; ~0 < A[i] \leq 10^6~

Dữ liệu vào gồm 2 dòng, dòng thứ nhất là số lượng N phần tử, dòng thứ 2 lần lượt là N phần tử trong mảng A.

Input 01:

8
3 3 4 6 6 7 8 9

Output 01:

5

Lưu ý: Số nguyên dương cần in phải nằm trong khoảng từ min tới max + 1 của mảng

Input 02:

9
2 2 3 4 5 6 7 8 9

Output 02:

10

Nhập vào một mảng các số nguyên A có N phần tử, in ra tổng giá trị các số dương liên tiếp lớn nhất.

Ràng buộc: ~0 < N \leq 10^6~; ~-10^6 \leq A[i] \leq 10^6~

Dữ liệu vào gồm 2 dòng, dòng thứ nhất là số lượng N phần tử, dòng thứ 2 lần lượt là N phần tử trong mảng A.

Input 01:

10
5 1 4 1 3 -2 1 2 -3 10

Output 01:

14

Input 02:

10
5 1 4 1 3 -2 1 2 -3 20

Output 02:

20

Cho mảng A có N phần tử, hãy tìm dãy con liên tiếp dài nhất có tổng các phần tử bằng 0. Nếu có nhiều dãy con thỏa mãn thì in ra dãy con đầu tiên, in ra "NOT FOUND" nếu không có dãy con nào có tổng bằng 0

Ràng buộc: ~1 \leq N \leq 10^6~; ~-10^6 \leq abs(A[i]) \leq 10^6~

Input 01:

15
-4 1 2 -1 2 -3 -8 2 1 -2 -8 7 -5 2 8

Output 01:

-4 1 2 -1 2

Input 02:

4
1 2 3 -4

Output 02:

NOT FOUND

Cho dãy số A[] gồm có t phần tử. Ớ mỗi thao tác bạn có thể tăng các phần tử trong mảng lên 1 lượng là d đơn vị, hãy xác định số thao tác tối thiểu sao cho mảng trở thành một dãy tăng chặt. Ví dụ dãy 1 2 3 7 8 là một dãy tăng chặt, nhưng dãy 1 2 2 7 8 không phải là một dãy tăng chặt. Ví dụ với mảng ban đầu là 1 3 3 2 và d = 2, ta cần thực hiện thao tác thứ nhất thêm d vào phần tử thứ 3 trong mảng, mảng trở thành 1 3 5 2, ta tiếp thục thực hiện 2 thao tác thêm d vào phần tử thứ 4, mảng trở thành dãy tăng chặt là 1 3 5 6.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N và số d. Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: 1≤ N, d ≤ 10^4; 0 ≤ A[i] ≤ 10^6

Định dạng đầu ra: In ra số thao tác tối thiểu cần thực hiện để biến mảng thành dãy tăng chặt.

Input:

3 3
15 17 9

Output:

3

Cho mảng A[] gồm N số nguyên không âm và số K. Nhiệm vụ của bạn là hãy chia mảng A[] thành hai mảng con có kích cỡ K và N-K sao cho hiệu giữa tổng hai mảng con là lớn nhất. Ví dụ với mảng A[] = {8, 4, 5, 2, 10}, K = 2 ta có kết quả là 17 vì mảng A[] được chia thành hai mảng (4, 2) và (8, 5,10) có hiệu của hai mảng con là 23-6=17 là lớn nhất.

Định dạng đầu vào: Dòng đầu tiên là 2 số N và K. Dòng thứ 2 là N số trong mảng A

Ràng buộc: 1 ≤ K < N ≤ 10^5; 0 ≤ A[i] ≤ 10^7

Định dạng đầu ra: In ra hiệu lớn nhất có thể.

Input:

8 3
1 1 1 1 1 1 1 1

Output:

2

Cho một dãy gồm n số nguyên dương a1, a2, a3,..., a_n là hoán vị của các số nguyên từ 1 đến n. Sử dụng các thao tác lần lượt đổi chỗ hai số ở vị trí i và j bất kỳ, hãy sắp xếp dãy ban đầu thành dãy tăng dần.

Input:

• Dòng đầu tiên chứa số nguyên dương n (n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương a1, a2, a3, ..., an là hoán vị của các số nguyên từ 1 đến n.

Output:

• Dòng đầu tiên in ra số k (0 ≤ k ≤ 2 x 10^5) - số lượng thao tác cần dùng.

• K dòng tiếp theo, mỗi dòng chứa hai số nguyên i, j cách nhau một khoảng trắng (1 ≤ i, j ≤ n) thể hiện một thao tác đối ai và aj cho nhau.

Có thể chứng minh được rằng luôn tồn tại cách sắp xếp thoa mãn không sử dụng quá 2 x 10^5 thao tác

Input:

4
3 4 1 2

Output:

2
1 3
2 4

Cho dãy số nguyên A (có thể chứa số âm). Hãy tìm một dãy con liên tiếp có tổng lớn nhất.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: Dãy A.

Dữ liệu ra:

Tổng lớn nhất tìm được.

Ràng buộc:

1 <= N <= 10^5

Ví dụ:

Input:

5 
-3 4 -1 2 1

Output:

6

Giải thích: Dãy con [4, -1, 2, 1] có tổng là 6.

Nhập 1 số nguyên dương N, sau đó nhập tiếp 1 dãy gồm N số nguyên. Tìm cặp đôi liên tiếp có khoảng cách lớn nhất.

Ghi ra khoảng cách lớn nhất đó.

Input:

• Dòng đầu tiên chứa số nguyên dương N (2 ≤ N ≤ 10^5).

• Dòng tiếp theo chứa N số nguyên x (|x| ≤ 10^9).

Output:

In ra khoảng cách lớn nhất.

Input:

4
1 3 5 10

Output:

5

Trong đợt nghỉ hè này, HCN được giao nhiệm vụ thống kê và báo cáo nhiệt độ của các ngày trong một tuần. Việc thống kê thì đã quá dễ dàng vì HCN có thể Google và hàng chục triệu kết quả sẽ hiện ra trước mắt. Nhưng còn việc viết báo cáo, vì HCN mải chơi và lười nghĩ nên HCN quyết định nhờ các bạn đọc thực hiện công việc hộ HCN.

Một bản báo cáo nhiệt độ cần có các thông tin sau:

• Nhiệt độ của các ngày lạnh hơn 10°C.

• Nhiệt độ của ngày lạnh nhất và nóng nhất.

Vậy đó, mặc dù biết cổ xuý cho việc lười biếng là không tốt, các bạn giúp HCN lần này nhé :-)

Input: Gồm bảy số thực lần lượt là nhiệt độ của các ngày trong tuần.

Output:

Dòng thứ nhất in ra nhiệt độ của các ngày lạnh hơn 10°C. Nếu có nhiều ngày thỏa mãn thì in theo thứ tự ngày trong tuần.

Dòng thứ hai in ra nhiệt độ của ngày lạnh nhất.

Dòng thứ ba in ra nhiệt độ của ngày nóng nhất.

Input:

12.8 15.3 20.1 15.9 9.0 8.9 12.6

Output:

9.0 8.9
8.9
20.1