Hè này, An xây dựng cho mình kế hoạch luyện tập chủ động trên một hệ thống lập trình trực tuyến. Hệ thống cung cấp ~N~ bài toán, hai bài toán có nội dung liên quan được sắp xếp liền kề nhau. Các bài toán có độ khó lần lượt là ~A_1,A_2,...,A_N~. An đặt ra mục tiêu là kết thúc đợt nghỉ hè phải ôn luyện được một số nội dung nên phải làm được các bài toán liên quan và có tổng độ khó lớn hơn hoặc bằng S. Do trong hè còn có nhiều hoạt động khác, An cũng muốn mình phải làm ít nhất các bài toán mà vẫn đạt mục tiêu đặt ra.

Yêu cầu Hãy giúp An tính ra số lượng bài toán ít nhất liên tiếp nhau cần phải làm để đạt tổng độ khó tối thiểu là ~S~.

Dữ liệu vào

• Dòng 1: Chứa hai số nguyên ~N~ và ~S~.(~1 \le N \le 10^7,1 \le S \le 10^{16}~)
• Dòng 2: chứa N số nguyên dương ~A_1,A_2,...,A_N~ (~1 \le A_i \le 10^9~)

Dữ liệu ra

• Dòng 1: Một số nguyên là số lượng bài toán An cần làm. Trường hợp không có phương án thỏa mãn, ghi ra số -1.

Ví dụ

Input1

10 18
5 1 3 9 10 7 4 9 2 8

Output1

2

Input2

5 27
2 3 5 1 9

Output2

-1

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

Yêu cầu: Hãy đếm số lượng các dãy con gồm các phần tử liên tiếp nhau có tổng bằng K tìm được.

Input:

• Dòng 1. Ghi 2 số nguyên 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 d là số lượng các dãy con có tổng bằng K tìm được thỏa mãn các yêu cầu trên.

(Lưu ý: 1 phần tử cũng tính là 1 dãy)

Example:

Input:

4  5
1 4 2 3

Output:

2

Constraints:

~0 < n < 2.10^4, -2.10^9 < k < 2.10^9; -10^7 \le a_i \le 10^7~

Nhân dịp kỉ niệm 1 năm thành lập, Câu lạc bộ tin học qboj tổ chức trò chơi "Dãy con kì diệu" dành cho các thành viên.

Trò chơi được tổ chức như sau:

Cho trước dãy số ~A~ gồm có ~𝑛~ phần tử là số nguyên dương có giá trị không vượt quá ~10^9~ và số ~𝑡~. Một dãy con ~𝑎_ℎ,𝑎_{ℎ+1},…,𝑎_{𝑟-1},𝑎_𝑟~ của dãy số ~A~ được xem là dãy con kì diệu nếu với mỗi cặp (~𝑖,𝑗~) thỏa mãn ~ℎ < 𝑖 < 𝑗 < 𝑟~ và ~|𝑎_𝑖-𝑎_𝑗|≤𝑡~. Hãy tìm dãy con kì diệu dài nhất của dãy số ~A~, độ dài dãy con đó chính là giá trị món quà mà người thắng cuộc (tức là người tìm đúng và nhanh nhất) sẽ nhận được.

Hãy giúp ban tổ chức trong việc chuẩn bị quà một cách nhanh nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi 2 số ~𝑛~ và ~𝑡~ (~1 ≤ 𝑛 ≤ 10^6,0 ≤ t ≤ 10^7~);

• Dòng thứ hai ghi ~𝑛~ số nguyên dương là giá trị ~𝑛~ phần tử của dãy số ~𝑎~;

• Các số trên mỗi dòng được ghi cách nhau ít nhất một ký tự trống.

Kết quả:

• Một số duy nhất là độ dài của dãy con kì diệu dài nhất tìm được của dãy số ~A~. Nếu không tìm được dãy thoả mãn thì in ra số 0.

Ví dụ

Input

9  3
15  1  3  5  8  6  7  9  10

Output

4

Cồn Nổi là một đảo thuộc vùng biển huyện Kim Sơn, tỉnh Ninh Bình. Nơi đây đang được đầu tư xây dựng và hứa hẹn trở thành một điểm du lịch, nghỉ dưỡng hấp dẫn. Trong một lần đến thăm Cồn Nổi, Minh Dương đi dạo dọc bờ biển và nhặt được những vỏ ốc có kích thước tương ứng là các số ~a_1,a_2,…,a_n~. Minh Dương muốn lựa chọn một số vỏ ốc để xâu lại thành một chuỗi, sao cho khi tính từ đầu chuỗi đến cuối chuỗi các vỏ ốc phía sau có kích thước lớn hơn vỏ ốc phía trước.

Yêu cầu: Hãy tìm số vỏ ốc nhiều nhất mà Minh Dương có thể chọn được.

Dữ liệu vào:

• Dòng đầu là số nguyên dương ~n~ (~n ≤ 10^6~).
• Dòng thứ hai ghi dãy các số nguyên dương ~a_1,a_2,…,a_n~ (~a_i \le 10^9, 1 \le i \le n~).

Dữ liệu ra:

• Ghi số vỏ ốc nhiều nhất mà Minh Dương có thể xâu được thành chuỗi.

Ví dụ:

Input1

6
6 5 8 8 3 6

Output1

4

Input2

8
6 1 2 2 7 6 2 5

Output2

5

Ràng buộc:

• 60% test với ~0 \le n,a_i \le 10^3~;
• 20% test với ~10^3 < n,a_i \le 10^5~;

Cho một mảng số nguyên ~A~ có ~N~ phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm vị trí của hai phần tử khác nhau bất kỳ sao cho tổng của chúng có giá trị là ~X~. Nếu trong dãy ~A~ không tồn tại hai phần tử khác nhau có tổng là ~X~ thì in ra "No solution".

Input

• Dòng đầu chứa 2 số nguyên ~N~ và ~X~.
• Dòng tiếp theo chứa ~N~ số nguyên ~A_i~.

Output

• Hai vị trí ~i~ và ~j~ khác nhau và xa nhau nhất có thể sao cho tổng ở hai vị trí này có giá là ~X~. In vị trí phần tử nhỏ hơn trước phần tử lớn hơn.
• Nếu không tồn tại in ra "No solution".

Constants

~N \le 10^6; A_i,X \le 10^9~

Example

Output

6 16
2 3 5 7 9 12

Output

4 5

Cu Tí thường xuyên tham gia thi lập trình trên mạng. Vì đạt được thành tích cao nên Tí được gửi tặng một phần mềm diệt virus. Nhà sản xuất phần mềm cung cấp cho Tí một mã số là một số nguyên dương có n chữ số. Để cài đặt được phần mềm, Tí phải nhập vào mật khẩu của phần mềm. Mật khẩu là một số nguyên dương M có giá trị lớn nhất được tạo ra bằng cách xoá đi k chữ số trong n chữ số đã cho, các chữ số còn lại vẫn giữ nguyên thứ tự.

Input:

• Dòng 1. Ghi 2 số nguyên dương n và k.
• Dòng 2: Ghi số nguyên dương có n chữ số.

Output:

• Dòng 1: Ghi số nguyên dương là mật khẩu tìm theo yêu cầu trên.

Example:

Input:

5 3
84915

Output:

95

Constraints:

~5 \le k \le n \le 32000~

Cho hai số nguyên dương N, S và dãy gồm N số nguyên dương đã được sắp xếp không giảm.

Yêu cầu: Đếm số lượng các cặp số ~A_i, A_j~ khác nhau sao cho tổng của chúng bằng S.

Lưu ý: các số chỉ được dùng 1 lần, nếu đã xuất hiện trong 1 cặp nào đó thì không được sử dụng lại

Input:

• Dòng đầu gồm 2 số nguyên dương N và S.
• Dòng thứ hai gồm N số nguyên dương ~A_1, A_2,...,A_N~ được sắp xếp không giảm.

Output:

• In ra số nguyên là số lượng các cặp số thoả mãn điều kiện.

Example:

Input:

4 6
1 1 5 5

Output:

2
Giải thích: Có 2 cặp số khác nhau có tổng bằng 6 đó là các cặp ở các vị trí (1,3) và (2,4)

Constraints:

~0 < N \le 10^6; 0 \le k, A_i \le 10^9~

Cho một mảng đã sắp xếp không giảm và số S, tìm cặp trong mảng mà có tổng gần S nhất

Input:

• Dòng đầu gồm 2 số nguyên dương N và S.
• Dòng thứ hai gồm N số nguyên dương ~A_1, A_2,...,A_N~ được sắp xếp không giảm.

Output:

• In ra tổng cặp số thoả mãn điều kiện.

Example:

Input:

6 70
10 20 35 50 75 80

Output:

70

Constraints:

~0 < N \le 10^6; 0 \le A_i \le 10^9; 0 \le S \le 2.10^9~

Cho hai dãy số nguyên đã được sắp xếp không giảm a và b lần lượt có n và m phần tử. Hãy ghép chúng thành dãy c được bố trí theo thứ tự không giảm.

Input:

• Dòng 1. Ghi 2 số nguyên dương ~n,m~.
• Dòng 2. Ghi n số nguyên ~a_1, a_2,...,a_n~
• Dòng 3. Ghi m số nguyên ~b_1, b_2,...,b_m~

Output:

• Ghi ra dãy số c theo yêu cầu bài toán.

Example:

Input:

3 4
1 3 4
1 2 3 5

Output:

1 1 2 3 3 4 5 

Constraints:

~n,m \le 10^5; 0 \le a_i,b_i \le 10^9~

Cho dãy số nguyên dương a có n phần tử. Hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không quá s. Dữ liệu đảm bảo các phần tử trong dãy a đều có giá trị không quá s.

Input:

• Dòng 1. Ghi 2 số nguyên dương n, s.
• Dòng 2. Ghi n số nguyên ~a_1, a_2,...,a_n~

Output:

• Ghi ra độ dài của dãy con dài nhất thoả mãn yêu cầu trên.

Example:

Input:

7 20
2 6 5 3 6 8 9

Output:

4

Constraints:

~n \le 10^6; 0 \le a_i \le 10^9; s \le 10^{18}~