Cho dãy số ~a_1,a_2,…,a_n~. Đếm số đoạn con liên tiếp có tổng không lớn hơn ~k~.

Lưu ý: 1 phần tử cũng được tính 1 đoạn con.

Dữ liệu vào:

• Dòng đầu tiên gồm 2 số nguyên dương ~n~ và ~k~. (~n≤10^6,1≤k≤10^9~)
• Dòng tiếp theo ghi ~n~ số lần lượt là ~a_1,a_2,…,a_n~. (~1 ≤ a_i≤10^9~)

Dữ liệu ra:

• Ghi số nguyên dương ~x~ duy nhất là số đoạn con có tổng không lớn hơn ~k~.

Ví dụ

Input:

5 100 
124 1 94 15 20

Output:

6

Cho dãy số nguyên dương ~a_1,a_2,…,a_n~ đã được sắp xếp tăng dần và số nguyên dương ~k~. Tìm 2 số ở vị trí ~i~, ~j~ gần nhất sao cho tổng ~a_i+a_j~ (~i<j~) có giá trị đúng bằng ~k~. </p>

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương ~n~ (~1 < n ≤ 10^6~) và số nguyên dương ~k~.
• Dòng tiếp theo ghi ~n~ số nguyên dương lần lượt là ~a_1,a_2,…,a_n~.

Dữ liệu ra:

• Dòng duy nhất in ra 2 số nguyên dương lần lượt là giá trị ~i~, ~j~ thỏa mãn. Nếu không có cặp giá trị thỏa mãn, in ra -1.

Input:

5 6
1 2 4 6 10

Output:

2 3

Cho dãy số ~a_1,a_2,…,a_n~. Hỏi tồn tại bao nhiêu cặp ~l~, ~r~ thỏa mãn sao cho mọi phần tử trong đoạn [~l,r~] (~l ≤ r~) đều đôi một khác nhau.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~t~ – số test case (~1≤ t ≤ 100~).
• Dòng đầu tiên của mỗi test case chứa số nguyên dương ~n~ (~1≤ n ≤ 200000~).
• Dòng tiếp theo chứa ~n~ số nguyên lần lượt là ~a_1,a_2,…,a_n~ (~1≤ a_i ≤ 10^9~).

Dữ liệu ra:

• Gồm ~t~ dòng, mỗi dòng là một số nguyên dương ~x~ duy nhất với ~x~ là số cặp ~l – r~ thỏa mãn tất cả các phần tử trong đoạn [~l,r~] đều đôi một khác nhau.

Ví dụ:

Input

2
5
1 2 3 3 4
5
2 2 3 3 4

Output

9
7