Cho dãy n số nguyên dương ~a_1~, ~a_2~,….,~a_n~ và số nguyên dương S.

Yêu cầu: Hãy đếm xem có bao nhiêu cặp phần tử (~a_i~, ~a_j~) (i <> j) thỏa mãn ~a_i+ a_j = S~.

Input:

• Dòng 1. Nhập số nguyên dương n và s
• Dòng 2. Nhập n số nguyên ~a_1~, ~a_2~,….,~a_n~

Output:

• Ghi số nguyên dương là kết quả bài toán.

Example:

Input:

5 4              
1  3  1  2  2

Output:

3

Constraint:

~n \le 10^5~ ; ~s~, ~a_i \le 10^6~

Cho 2 số nguyên dương N,K và dãy gồm N số nguyên. Hãy tìm xem có bao nhiêu cặp số có chênh lệch đúng bằng K.

Input:

Được chọ bởi tệp CHENHLECH.INP có cấu trúc:

• Dòng đầu tiên gồm 2 số nguyên dương N,K ~(2 \le N \le 10^6; 0 \le k \le 10^9)~

• Dòng thứ hai gồm N số nguyên dương ~ 0 \le A_i \le 10^9~;

Output:

Được chọ bởi tệp CHENHLECH.OUT có cấu trúc:

• In ra số nguyên X là số cặp có độ chênh lệnh đúng bằng K.

Example:

Input:

6  2
1 3 2 4 9 5

Output:

3
Giải thích: có 3 cặp đó là: (1,3) (3,5) (2,4)

Constraints:

• Subtask 1 (50% số điểm): ~N \le 10^4~

• Subtask 2 (50% số điểm): không ràng buộc gì thêm.

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

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

Một ngày lướt fb, TN thấy một đôi couple chia sẻ bài bói toán online, rằng đôi couple kia hợp nhau thế nào, yêu nhau ra sao, vân vân và mây mây. Tò mò không biết âm dương ngũ hành, yêu nhau hợp tình nghĩa không, TN cũng bảo Ami cùng mình tham gia bói toán online. Nhưng Ami đời nào tin những thuật toán tào lao ấy? "Bởi vì không một thuật toán nào định nghĩa được tình yêu cả" – Ami nói. Cậu bèn dẫn TN đến cặp thầy bói nổi danh thiên hạ - zerolifes và huyyeuminh_nghia. Hai lúc nào cũng hơn một mà :)).

Sau khi xem chỉ tay, tướng số, ngũ hành, chiêm tinh, zerolifes không nói không rằng. Anh đọc liên tục 1 câu thần chú chỉ toàn những con số vô nghĩa nhưng không giảm. Đột nhiên zerolife dừng lại, huyyeuminhnghia hét lên một số :30. Nhưng 30 là gì ? Không lẽ 2 vị này cao thâm đến mức biết ngày mình và TN quen nhau sao?, Ami thầm nghĩ, Hay 30 là số tỉ USD mà sau này mình tậu được ? Không, không thể ít như vậy được. Không thể kìm nén, Ami thỉnh cầu 2 vị cao nhân. Zerolifes nói :Đơn giản thôi, âm dương hòa hợp, trong cương có nhu, trong nhu có cương, cậu hãy ghi nhớ dãy số của ta và số mà huyyeuminhnghia vừa đọc, hãy đếm xem trong dãy số của ta có bao nhiêu cặp số có tổng đúng bằng k. Nếu số cặp càng lớn, khả năng hai người bền lâu càng nhiều. Tất nhiên, Ami không dám làm ngay lập tức, vì sợ sự thật có thể làm cậu suy sụp.

Tóm lại, có một dãy gồm n số nguyên dương không giảm ~a_1,a_1,a_3,...a_n~ và một số k, Ami muốn đếm số cặp (~i~, ~j~) không trùng nhau mà ~a_i + a_j= k~, lưu ý rằng (i,(~i~, ~j~) và (~j~, ~i~) được tính là 1 cặp.

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~ (n(~n ≤10^6,k ≤10^9~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_1,a_3,...a_n~(~a_i≤10^9~).

Output

• Hãy in ra một số nguyên là kết quá của bài toán.

Example

Test 1

Input

4 6
1 1 5 5

Output

4

Test 2

Input

6 5
1 1 1 4 5 5

Output

3

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 dãy số gồm ~n~ số nguyên ~a_1, a_2, a_3,…, a_n~ và một số nguyên dương ~k~.

Yêu cầu: Đếm các cặp số (~i~ ; ~j~) thỏa mãn: ~i < j~ và ~a_i + a_j~ chia hết cho ~k~.

Dữ liệu vào:

• Dòng đầu: Gồm 2 số nguyên dương ~n~, ~k~ (~n, k < 10^6~), mỗi số cách nhau một khoảng trắng.
• Dòng thứ hai: Dãy số nguyên ~a_1, a_2, a_3,…, a_n~ (~|a_i| <10^6; 1\le i \le n~), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra:

• Số nguyên duy nhất theo yêu cầu.

Ví dụ:

Input

5 6
2 4 5 8 -2

Output

4

Giải thích:

• Có 4 cặp (i ; j) là (1 ; 2), (1 ; 5), (2 ; 4), (4 ; 5)

Giới hạn dữ liệu:

• 60% bộ test với ~n <10^3~
• 40% bộ test không giới hạn gì thêm.

Cho dãy a gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3. Nói cách khác, bạn phải đếm xem có bao nhiêu cặp chỉ số ~i, j~ (~1 ≤ i < j ≤ n~) sao cho tổng ~a_i + a_j~ chia hết cho 3.

Dữ liệu vào:

· Dòng 1: Một số nguyên duy nhất ~n~ (~1 ≤ n ≤ 5.10^6~).

· Dòng 2: Ghi n số nguyên dương ~a_1,a_2,...,a_n~(~1 ≤ a_i ≤ 10^{18}~) là các phần tử của dãy.

Kết quả:

· Một dòng duy nhất ghi số lượng cặp số của dãy ~a~ có tổng chia hết cho ~3~.

Ví dụ:

Input1

5
3 4 2 3 4

Output1

3

Input2

4
3 6 9 12

Output2

6

Cô giáo trường tiểu học X đang dạy N học sinh tập xe đạp, các học sinh được đánh số từ 1 tới N, học sinh thứ 𝑗 có trọng lượng là A𝑗. Có một xe đạp duy nhất với tải trọng là m, hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá m. Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán trên.

Yêu cầu: Đếm số cặp chỉ số i, j trong đó i < j và ~A_i + A_j \le M~

Input:

• Dòng 1 chứa hai số nguyên dương N,M (~ N,M \le 10^6~)
• Dòng 2 chứa N số nguyên dương ~A_1, A_2,…A_N~ (~A_i \le 10^6~)

Output:

• Ghi một số nguyên duy nhất là đáp số

Example:

Input:

5 6
1 2 3 4 5

Output:

6

Constraints:

• Subtask #1 (60% số điểm): ~n \le 10^4~.

• Subtask #2 (20% số điểm): ~n \le 10^5~.

• Subtask #3 (20% số điểm): ~n \le 10^6~.

Tết năm nay, Đồng Hới có phố đi bộ, dọc theo tuyến phố có N địa điểm vui chơi, các địa điểm được đánh số lần lượt từ 1 đến N tính từ đầu phố. Sắp tới trên tuyến phố được trang bị thêm xe điện để dưa đón du khách. Ban đầu, Ban quản lý dự kiến bố trí 2 trạm dừng tại 2 trong số n địa điểm vui chơi, đồng thời để 2 trạm này không quá gần nhau, khoảng cách giữa 2 trạm phải lớn hơn r.

Yêu cầu: Đếm số cặp điểm vui chơi trên tuyến phố mà ban quản lý có thể chọn để đặt hai trạm dừng chân sao cho khoảng cách giữa 2 trạm lớn hơn ~r~.

Input:

• Dòng 1: chứa 2 số nguyên ~N,r~
• Dòng 2: chứa ~N~ số nguyên ~a_1, a_2,…..,a_N~.
• Với ~a_i~ là khoảng cách từ điểm vui chơi thứ i đến đầu con phố, các số cách nhau bởi 1 ký tự trống.

Output:

• In ra số lượng cặp điểm mà ban quản lý có thể chọn để đặt 2 trạm dừng chân.

Example:

Input:

4 4
1 3 5 8

Output:

2
Giải thích: Có 2 phương án chọn đó là (1,4) ; (2,4)

Constraints:

~2 \le N \le 10^5; 1 \le r, a_i \le 10^9~