Cho một mảng ~a~ gồm ~n~ số nguyên, hãy tìm đoạn con liên tiếp dài đúng ~L~ có tổng lớn nhất.

• Một đoạn con dài ~L~ là [~a_i, a_{i+1}, ..., a_{i+L-1}~] với ~1 ≤ i ≤ n-L+1~
• Tính tổng lớn nhất của tất cả các đoạn con dài đúng ~L~.

Input

• Dòng 1: hai số nguyên ~n~ và ~L~ (~1 ≤ L ≤ n ≤ 2×10^5~)
• Dòng 2: mảng ~a[1] a[2] … a[n]~, mỗi phần tử ~-10^9 ≤ a[i] ≤ 10^9~

Output

• Một số nguyên: tổng lớn nhất của đoạn dài ~L~

Ví dụ

Input1:

5 3
1 2 3 1 2

Output1:

6

Giải thích:

Các đoạn dài 3:

[1,2,3] → tổng = 6

[2,3,1] → tổng = 6

[3,1,2] → tổng = 6

→ Tổng lớn nhất = 6

Cho số nguyên dương k và một dãy gồm N số nguyên dương ~a_1, a_2, ..., a_N~. Hãy tìm số cặp số nguyên (~l~, ~r~) với ~1 ≤ l ≤ r ≤ N~ sao cho trong đoạn con từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.

INPUT

• Dòng 1: ~N~, ~k~ (~1 ≤ N ≤ 3×10^5~, ~1 ≤ k ≤ 10^9~)
• Dòng 2: ~a_1, a_2, ... ,a_N~ (~1 ≤ a_i ≤ 10^9~)

OUTPUT

• Một số nguyên: số lượng cặp (~l~, ~r~) thỏa mãn điều kiện.

VÍ DỤ

Input:

5 2
1 2 3 4 5

Output:

11

Cho hai xâu ký tự ~S~ và ~T~ chỉ gồm các chữ cái in hoa tiếng Anh (~A–Z~).

Hãy tìm xâu con liên tiếp ngắn nhất của ~S~ sao cho xâu con đó chứa tất cả các ký tự của ~T~, bao gồm cả số lần xuất hiện của từng ký tự.

Nếu có nhiều xâu con thỏa mãn, hãy in ra xâu có độ dài nhỏ nhất. Nếu không tồn tại, in ra xâu rỗng.

Dữ liệu vào

• Dòng 1: xâu ~S~ (~1≤∣𝑆∣≤10^5~)
• Dòng 2: xâu ~T~ (~1≤∣𝑇∣≤10^5~)

Dữ liệu ra

• In ra xâu con ngắn nhất của ~S~ thỏa mãn yêu cầu. Nếu không tồn tại, in ra xâu rỗng (không in gì)

Ví dụ

Input1:

ADOBECODEBANC
ABC

Output1:

BANC

Input2:

AAABBC
ABC

Output2:

ABBC

Cho xâu ~S~ độ dài ~n~. Hãy tìm xâu con dài nhất của ~S~, sao cho mỗi ký tự tham gia vào xâu con không quá ~k~ lần (~1 ≤ n ≤ 100 000~, ~1 ≤ k ≤ n~).

Yêu cầu: Chỉ ra độ dài của xâu con tìm được và vị trí của ký tự đầu tiên thuộc xâu con trong xâu S ban đầu. Nếu có nhiều cách chọn xâu con – chỉ ra cách chọn xâu con với vị trí bắt đầu là nhỏ nhất.

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~k~.

• Dòng thứ hai chứa xâu ~S~.

Kết quả:

• Một dòng chứa hai số nguyên: độ dài xâu con và vị trí ký tự đầu tiên của xâu con. Nếu có nhiều xâu con thì ghi vị trí của xâu con đầu tiên trong dãy.

Ví dụ:

Input

5 2
ababa

Output

4 1

Sau khi thi giữa kì, vì đạt điểm số "cao", cụ thể là 5 6 7 8 nên Tèo được mẹ thưởng một chuyến đi du lịch ở "Dream Land".

Ở công viên giải trí "Dream Land", người ta có bán ~m~ vé khác nhau và mỗi loại vé được đánh số từ 1 tới ~m~. Các loại vé có giá tiền bằng nhau và chỉ còn bán với mỗi loại một lần sẽ có hiệu lực vĩnh viễn (sử dụng không giới hạn). Tèo được mẹ cho ~k~ ngày để giải trí tại đây, Tèo nghĩ rằng sẽ rất tệ nếu các ngày vui chơi bị gián đoạn nên Tèo mong muốn được vào khu vui chơi ~k~ ngày liên tiếp. Tèo được cung cấp một dãy ~n~ số nguyên ~a₁, a₂, ..., aₙ~ ~(1 ≤ aᵢ ≤ ~m) cho biết loại vé cần thiết vào ngày thứ ~i~.

Yêu cầu: Hãy giúp Tèo tìm số lượng vé ít nhất phải mua để có thể vào "Dream Land" vui chơi ~k~ ngày liên tiếp.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~t~ (~1 ≤ t ≤ 100~) là số bộ test, trong mỗi bộ test:

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

• Dòng thứ hai chứa n số nguyên ~a₁, a₂, ..., aₙ~ ~(1 ≤ aᵢ ≤ m~).

• Tổng ~n~ trong tất cả các test không quá ~10^5~.

Kết quả ra

• Một dòng duy nhất chứa số lượng vé ít nhất phải mua thỏa yêu cầu đề bài.

Ví dụ:

Input

3
10 6 6
6 1 6 4 4 6 5 3 4 4
8 2 4
2 1 2 1 2 1 2 1
1 4 1
3

Output

3
2
1

Giải thích

• Ở test đầu tiên, Tèo chọn đi chơi từ ngày 1 đến ngày 6 và cần 3 loại vé là 1, 6, 4.

• Ở test thứ hai, Tèo có thể chọn 4 ngày liên tiếp bất kỳ và cần 2 loại vé là 1, 2.

• Ở test cuối, Tèo chỉ có một lựa chọn duy nhất là mua 1 loại vé số 3.

Cho một dãy số nguyên dương ~𝐴~ = (~𝑎_1, 𝑎_2, … , 𝑎_𝑛~) (~𝑎_𝑖 ≤ 10^6; 1 ≤ 𝑖 ≤ 𝑛~). Với mỗi phần tử ~𝑎_𝑖~ bạn được phép tăng hoặc giảm một lượng tùy ý để được một số nguyên tố. Khi đó chi phí của bạn cần bỏ ra chính là lượng tăng hoặc giảm đó.

Yêu cầu: Hãy chọn ra một đoạn con gồm ~𝑘~ phần tử liên tiếp nhau của dãy ~𝐴~ sao cho tổng chi phí biến đổi mọi phần tử trong đoạn con đó thành các số nguyên tố là nhỏ nhất.

Dữ liệu vào:

• Dòng 1: Chứa hai số nguyên dương ~𝑛~, ~𝑘~ (~1 ≤ 𝑘 ≤ 𝑛 ≤ 10^5~);
• Dòng 2: Chứa ~𝑛~ số nguyên dương ~𝑎_1, 𝑎_2, . . , 𝑎_𝑛~ (~𝑎_𝑖 ≤ 10^6~ ~∀𝑖 = 1,2, … , 𝑛~).

Dữ liệu ra:

• Gồm một số nguyên duy nhất là tổng chi phí biến đổi nhỏ nhất tìm được.

Ví dụ:

Input

4 2 
9 5 8 15  

Output

1

Giải thích:

• Chọn đoạn [5,8], biến đổi 8 → 7 với chi phí là 1.

Ràng buộc:

• Subtask1: Có 20% số test có ~𝑎_𝑖~ đều là số nguyên tố ~∀ 𝑖~ = 1,2, … , ~𝑛~.
• Subtask2: 40% số test ~𝑛~, ~𝑘~ ≤ 5000; ~𝑎_i ≤ 5000~ ~∀ 𝑖~ = 1,2, … , ~𝑛~.
• Subtask3: 40% số test còn lại không có ràng buộc gì thêm.

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ố 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

Cho dãy số nguyên dương 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 đều có giá trị không quá .

Dữ liệu vào:

• 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~.

Giới hạn: ~1 \le N \le 10^6~; ~1 \le a_i \le 10^9~; và ~1 \le S \le 10^{18}~.

Ví dụ:

Input

5 15
1 2 3 4 6

Output

4

Cho trước mảng số nguyên ~a~.

Yêu cầu: Hãy loại bỏ các phần tử trùng lặp trong dãy và đưa ra độ dài của dãy mới?

Input:

• Dòng đầu tiên chứa số nguyên dương ~n~ - kích thước dãy số.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,…,a_n~ phân tách nhau bởi dấu cách - các phần tử dãy số.

Output:

• In ra số lượng các phần tử khác nhau trong dãy ~a~.

  Ràng buộc:

• ~1 ≤ n ≤ 10^5~ ; ~0 \le a_i \le 10^9~

Ví dụ:

Input

5
1 2 3 4 4

Output

4

Cho số nguyên dương ~𝑛~ và dãy số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.

Yêu cầu: Hãy cho biết có bao nhiêu dãy con gồm các phần tử liên tiếp nhau có tổng đúng bằng ~𝑘~.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương ~𝑛~, ~𝑘~ (~1 ≤ 𝑛 ≤ 10^6; 𝑘 ≤ 10^9~)
• Dòng thứ hai ghi lần lượt các số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~(~1 ≤ 𝑎_𝑖 ≤ 10^6~)

Kết quả:

• Ghi một số nguyên cho biết kết quả bài toán.

Ví dụ:

Input

6 8
4 3 5 2 1 8 

Output

3

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm có ~𝑛 ≤ 200~;
• Có 30% số test khác tương ứng 30% số điểm có ~𝑛 ≤ 2000~;
• Có 20% số test khác tương ứng 20% số điểm có ~𝑛 ≤ 2 × 10^5~;
• Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm

Cho hai số nguyên dương n,m và hai dãy số nguyên ~a_1,a_2,…,a_n~; ~b_1,b_2,…b_m~.

Yêu cầu: Hãy cho biết mỗi số ~b_j~(~j=1...m~) xuất hiện bao nhiêu lần trong dãy ~a_1,a_2,…,a_n~.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên ~n~,~m~.

• Dòng thứ hai ghi lần lượt các số ~a_1,a_2,…,a_n~.

• Dòng thứ ba ghi lần lượt các số ~b_1,b_2,…,b_m~

Kết quả

Ghi m số trong đó số thứ ~j~(~j=1..m~) là số lượng của giá trị bj trong dãy ~a_1,a_2,…,a_n~;

Ràng buộc

~1 ≤ n,m ≤ 10^5~; ~|a_i| ≤ 10^9~;~(i=1...n)~; ~|b_j|≤10^9;(j=1...m)~

Ví dụ:

Input

5 3
1 2 2 5 3
2 6 1 

Output

2 0 1 

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}~

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~ xa 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~. Đế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 một dãy gồm ~𝑛~ số nguyên dương ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~ và hai số nguyên dương p~, q~. Mỗi dãy ~𝑎_𝑖, 𝑎_{𝑖+1}, 𝑎_{𝑖+2}, . . . , 𝑎_𝑗~ với ~1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛~ được gọi là dãy con liên tiếp của dãy đã cho.

Yêu cầu: Hãy lập trình đếm số các dãy con liên tiếp của dãy số đã cho có tổng các số lớn hơn hoặc bằng ~p~ và nhỏ hơn hoặc bằng ~q~.

Dữ liệu vào:

• Dòng đầu ghi ba số nguyên ~𝑛, p, q~(~1 ≤ 𝑛 ≤ 10^5; 1 ≤ p, q ≤ 10^{18}, 𝑚 < 𝑀~);

• Dòng thứ hai ghi ~n~ số nguyên 𝑎, ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~(~1 ≤ 𝑎_𝑖 ≤ 10^7, 𝑖 = 1,2, . . . , 𝑛~).

  Kết quả:

• Ghi một số nguyên là số các dãy con liên tiếp thỏa mãn có tổng các số lớn hơn hoặc bằng ~p~ và nhỏ hơn hoặc bằng ~q~.

Ví dụ:

Input1

6 5 10
3 2 4 2 1 2

Output1

9

Input2

10 20 30
3 2 4 2 1 2 9 12 3 7

Output2

12

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 số nguyên dương ~𝑛~ và dãy số nguyên dương ~𝑎_1,𝑎_2,…,𝑎_𝑛~.

Yêu cầu: Hãy cho biết có bao nhiêu dãy con gồm các phần tử liên tiếp nhau có tổng đúng bằng ~𝑘~.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương ~𝑛,𝑘~ (~1≤𝑛≤ 10^7;𝑘≤10^9~)

• Dòng thứ hai ghi lần lượt các số ~𝑎_1,𝑎_2,…,𝑎_𝑛~ (~1 ≤ 𝑎_𝑖≤ 10^6~)

Kết quả:

• Ghi một số nguyên cho biết kết quả bài toán.

Ví dụ:

Input

6 8
4 3 5 2 1 8

Output

3

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 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 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 hai vị trí ~i,j~ khác nhau bất kỳ sao cho tổng của hai phần tử ở hai vị trí đó có giá trị là ~x~ và ~j-i~ lớn nhất có thể.

Input:

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

Output:

• Ghi ra cặp số ~i,j~ thoả mãn yêu cầu trên. Nếu không tìm ra được cặp số i,j thoả mãn thì in 'No solution'

Example:

Input:

7 16
2 5 6 8 10 12 15

Output:

3 5

Constraints:

~n \le 10^6; 0 \le a_i \le 10^9~

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 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~

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~