Cho trước 2 dãy A và B đều có N phần tử nguyên. Hãy chỉ ra một cặp số i, j có khoảng cách xa nhất sao cho tổng từ ~A_i~ đến ~A_j~ bằng tổng từ ~B_i~ đến ~B_j~.

Dữ liệu vào:

• Dòng 1. ghi số nguyên dương n
• Dòng 2: ghi n số nguyên của dãy A: ~A_1~, ~A_2~,….,~A_n~
• Dòng 3: ghi n số nguyên của dãy B: ~B_1~, ~B_2~,….,~B_n~

Kết quả:

• Dòng 1. ghi 2 số nguyên dương i và j lần lượt là vị trí bắt đầu và kết thúc của dãy tìm được, 2 số ngăn cách nhau bởi dấu cách. Nếu không tìm thấy dãy nào thỏa mãn thì ghi số 0.

Dữ liệu nhập:

5         
1  3  1  2  2
7  4  1  1  9

Output:

2 4

Constraints:

~n \le 10^4~ ; ~A_i~,~B_i \le 10^5~

Cho một dãy số nguyên A khác 0 có N số. Một đoạn con của dãy gồm các phần tử liên tiếp được gọi là đan dấu nếu trong đoạn con đó không có hai phần tử liên tiếp nào cùng dấu với nhau.

Yêu cầu: Hãy tính độ dài đoạn con dài nhất.

Input:

Được cho bởi tệp DOANCON.INP có cấu trúc như sau:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số ~A_1, A_2,…A_N~.

Output:

Được cho bởi tệp DOANCON.OUT có cấu trúc như sau:

• Dòng 1 chứa số K là kết quả của bài toán.

Example:

Input:

3
1 2 -2

Output:

2

Constraints:

~N \le 10^4; ∣A_i| \le 10^9~

Cho một dãy số nguyên A khác 0 có N số. Một đoạn con của dãy gồm các phần tử liên tiếp được gọi là cùng dấu nếu trong đoạn con đó không có hai phần tử liên tiếp nào trái dấu với nhau.

Yêu cầu: Hãy tính độ dài đoạn con dài nhất.

Input:

Được cho bởi tệp DOANCON3.INP có cấu trúc như sau:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số ~A_1, A_2,…A_N~.

Output:

Được cho bởi tệp DOANCON3.OUT có cấu trúc như sau:

• Dòng 1 chứa số K là kết quả của bài toán.

Example:

Input:

3
1 2 -2

Output:

2

Constraints:

~N \le 10^4; ∣A_i| \le 10^9~

Cho một dãy số nguyên A khác 0 có N số. Một đoạn con của dãy gồm các phần tử liên tiếp được gọi là tăng dần nếu trong đoạn con đó phần tử đứng sau luôn lớn hơn phần tử đứng trước.

Yêu cầu: Hãy tính độ dài đoạn con dài nhất.

Input:

Được cho bởi tệp DOANTANG.INP có cấu trúc như sau:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số ~A_1, A_2,…A_N~.

Output:

Được cho bởi tệp DOANTANG.OUT có cấu trúc như sau:

• Dòng 1 chứa số K là kết quả của bài toán.

Example:

Input:

5
1 2 3 3 4

Output:

3

Constraints:

~N \le 10^4; ∣A_i| \le 10^9~

Cho một dãy số nguyên A khác 0 có N số. Một đoạn con của dãy gồm các phần tử liên tiếp được gọi là giảm dần nếu trong đoạn con đó phần tử đứng sau luôn bé hơn phần tử đứng trước.

Yêu cầu: Hãy tính độ dài đoạn con dài nhất.

Input:

Được cho bởi tệp DAYGIAM.INP có cấu trúc như sau:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số ~A_1, A_2,…A_N~.

Output:

Được cho bởi tệp DAYGIAM.OUT có cấu trúc như sau:

• Dòng 1 chứa số K là kết quả của bài toán.

Example:

Input:

5
1 5 3 2 4

Output:

3

Constraints:

~N \le 10^4; ∣A_i| \le 10^9~

Cho một dãy các số nguyên A có N phần tử, hãy tìm đoạn con gồm các phần tử liên tiếp có tổng lớn nhất của dãy A này.

Input:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số, là miêu tả dãy A.

Output:

• Tổng của đoạn con có tổng lớn nhất tìm được.

Example:

Input

6
1 2 3 -1 -1 -1

Output

6

Constraint:

~0 < N \le 10^5; |A_i| \le 10^9~

Cho dãy a gồm n phần tử, hãy tìm đoạn con liên tiếp có tổng lớn nhất và độ dài đoạn con lớn hơn hoặc bằng k. In ra màn hình tổng lớn nhất vừa tìm được.

Input

• Dòng đầu gồm n ~(1 \le k \le n \le 10^6)~
• Dòng tiếp theo gồm n số, số thứ i là ai ~(-10^9 \le a_i \le 10^9)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Example

Input

6 5
2 -10 6 -5 2 4

Output

-1

Cho dãy số nguyên dương A có N phần tử: ~a_1, a_2, …, a_N~ và một số nguyên dương M ~(1 ≤ N \le 10000; 0 < a_i \le 32000; 0 < M \le 2×10^9)~.
Yêu cầu: Hãy tìm số nguyên d, d là số lượng các dãy con gồm các phần tử liên tiếp trong A sao cho tổng các phần tử của dãy con có giá trị bằng M.

Input:

Ghi trong file văn bản SUBSUM.INP

• Dòng đầu tiên: Ghi 2 số nguyên N và M.
• Dòng thứ hai: Ghi dãy số nguyên ~a_1, a_2, …, a_n~, các số được ghi các nhau ít nhất một dấu cách.

Output:

Ghi ra file văn bản SUBSUM.OUT theo cấu trúc như sau:

• Dòng đầu tiên: Ghi số nguyên d tìm được.

Example:

Input:

7   6
1   6   1   3   2   4   5 

Output:

3
Giải thích: 
Trong ví dụ trên: n = 7, m = 6, dãy A gồm 1  6  1  3  2  4  5 có 3 dãy con liên tiếp có tổng bằng m đó là:   6;   1  3  2;  2   4;  

Cho 2 số nguyên dương N,K và dãy gồm N số nguyên ~a_1, a_2,…a_n~.

Yêu cầu: Hãy in ra dãy con liên tiếp dài nhất các phần tử bằng k có trong dãy. (Lưu ý: dãy con phải có từ 2 phần tử trở lên)

Input:

• Dòng 1. Ghi 2 số nguyên dương N, K
• Dòng 2: Ghi N số nguyên mỗi số cách nhau ít nhất 1 dấu cách.

Output:

• Dòng 1. Ghi số nguyên dương P là độ dài dãy con tìm được thỏa mãn các yêu cầu trên. Nếu không tìm được dãy nào thỏa mãn thì ghi -1.

Example:

Input:

6 3
6 3 3 3 3 2

Output:

4

Constraints:

~0 < n < 100000; 0 < a_i \le 32000~

Cho lần lượt 2 số nguyên dương n, k và mảng a có n phần tử, hãy tìm tổng lớn nhất trong các dãy con liên tiếp độ dài k trong mảng.

Input:

• Dòng 1. Ghi 2 số nguyên dương n,k.
• Dòng 2. Ghi n số nguyên

Output:

• In ra tổng lớn nhất của dãy số có độ dài k tìm được.

Example:

Input:

8 4
0 9 3 8 2 4 0 9

Output:

22

Constraints:

~1 \le k \le n \le 10^6, 0 \le |a_i| \le 10^9~

Cho một mảng N số nguyên. Kiểm tra xem mảng có đối xứng không. Mảng đối xứng là mảng khi viết theo chiều xuôi hay ngược lại đều được kết quả giống nhau.

Input:

• Dòng đầu tiên là số nguyên N (1≤N≤106).

• Dòng thứ 2 là mảng N số nguyên, các số cách nhau bởi dấu cách, trị tuyệt đối của các số này không quá ~10^{18}~.

Output:

• Nếu mảng đối xứng in ra "TRUE", nếu không in ra "FALSE".

Example:

Input:

5
5 4 4 3 2

Output:

FALSE

Input:

3
4 2 4

Output:

TRUE

Công ty đồ chơi ~X~ nhập khẩu ~N~ con búp bê gỗ. Các con búp bê được đánh số từ 1 tới ~N~ trong đó con búp bê thứ ~i~ là một hộp rỗng có kích thước là một số nguyên ~A_i~. Người ta có thể lồng con búp bê thứ i vào trong con búp bê thứ ~j~ nếu con búp bê thứ ~j~ đang rỗng và ~A_i+k≤ A_j~, với ~K~ là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty ~X~ chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.

Yêu cầu: Hãy giúp công ty ~X~ lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.

Input:

Gồm 2 dòng:

• Dòng 1 chứa hai số nguyên dương cách nhau một khoảng trắng.

• Dòng 2 chứa n số nguyên dương ~A_1~, ~A_2~,...,~A_N~ , mỗi số cách nhau một khoảng trắng.

Output:

• Là một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.

Example:

Input:

8 2
8 4 2 1 1 3 5 9

Output:

18

Constraint:

~N \le 10^5~; ~K \le 10^9~; ~A_i ≤ 10^9~

Vaxia đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai Petia về thành quả vừa đạt được. Tuy nhiên, khi Vaxia vừa ra khỏi phòng để gọi anh trai thì cô em Kachia chạy vào phòng và xé rách cuộn giấy thành một số mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã viết. Bây giờ Vaxia không thể nhớ chính xác mình đã viết số gì. Vaxia chỉ nhớ rằng đó là một số rất lớn. Để làm hài lòng cậu em trai, Petia quyết định truy tìm số nào là lớn nhất mà Vaxia đã có thể viết lên cuộn giây trước khi bị xé. Bạn hãy giúp Petia làm việc này.

Input:

Được cho bởi tệp GHEPSO.INP có cấu trúc như sau:

• Ghi một hoặc nhiều dòng. Mỗi dòng ghi một dãy kí số. Số dòng không vượt quá 100. Mỗi dòng ghi từ 1 đến 100 kí số. Bảo đảm rằng có ít nhất một dòng mà kí số đầu tiên khác 0. (Số lượng các dòng không vượt quá 100000)

Output:

Được cho bởi tệp GHEPSO.OUT có cấu trúc như sau:

• Ghi ra số lớn nhất đã có thể viết trên cuộn giấy trước khi bị xé rách.

Example:

Input:

2
20
004
66

Output:

66220004

Cho một mảng nguyên dương có N phần tử. Ta sẽ thực hiện N - 1 thao tác. Ở mỗi thao tác, ta chọn hai phần tử bất kỳ trong dãy và xóa đi số lớn hơn (xóa số bất kỳ nếu chúng bằng nhau), và mất một khoản chi phí bằng số nhỏ hơn (nếu hai số bằng nhau chi phí bằng một trong hai số).

Yêu cầu: Hãy tính tổng chi phí ít nhất có thể sau khi thực hiện xong N - 1 bước.

Input:

• Dòng 1. Ghi số nguyên dương N.
• Dòng 2: Ghi n số nguyên của dãy A: ~A_1~, ~A_2~,….~A_N~

Output:

• Dòng 1. Ghi số nguyên dương K duy nhất là kết quả bài toán.

Example:

Input:

4
1 2 3 4

Output:

3

Constraint

~ 0 \le a_i \le 10^5~ ; ~1 \le N \le 10^5~

Cho dãy số nguyên a gồm ~n~ phần tử ~a_1, a_2, ..., a_n~.

Yêu cầu: Hãy tìm dãy con liên tiếp gồm các phần tử liên tiếp ~a_l, a_{l+1}, a_{l+2}, ... a_r~ (~1 ≤ l ≤ r ≤ n~) trong dãy a sao cho giá trị trung bình của nó là lớn nhất. Giá trị trung bình của dãy con: ~a_l, a_{l+1}, a_{l+2}, ... a_r~ được tính bằng công thức sau: ~(a_l, a_{l+1}, a_{l+2}, ... a_r)/(r-l+1)~. Nếu có nhiều dãy con như vậy thì hãy tìm dãy dài nhất.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương ~n~ là số phần tử của dãy ~a~.
• Dòng 2: Ghi n số nguyên ~a_1, a_2 ... a_n~, các số được ghi cách nhau một dấu cách.

Kết quả:

• Dòng 1: In ra một số nguyên là số phần tử của dãy con liên tiếp dài nhất và có giá trị trung bình lớn nhất có thể.

Ràng buộc:

~1 ≤ n ≤ 10^5~ ; ~0 ≤ a_i ≤ 10^9~ (~1 ≤ i ≤ n~)

Ví dụ:

Input

5
6 1 6 6 0

Output

2

Giải thích

• Dãy con liên tiếp dài nhất có giá trị trung bình lớn nhất trong dãy đã cho là dãy (6, 6) gồm 2 phần tử và có giá trị trung bình là (6+6)/(4-3+1) = 6.

Cho dãy số A có N số nguyên. Hãy đếm số cặp ~(i,j)~ t sao cho ~A_i + A_j = 0~, với ~i < j~.

Input

• Dòng đầu tiên chứa một số nguyên dương N ~(1 \le 2.10^5)~.
• Dòng thứ hai chứa dãy số A gồm N số nguyên cách nhau bởi một ký tự khoảng trống ~|a_i \le 10^9|~.

Output

• In ra một số nguyên duy nhất, là số cặp phần tử trong dãy A mà có tổng là 0.

Example

Input

3
-2 0 2

Output

1

Input

6
-2 -1 0 0 1 2

Output

3