Sum

Interview

Time limit1sMemory limit1024 MB

Summary

Count the pairs of distinct elements in a sorted array of N distinct integers that add up to S.

Level: Easy3 of 10
Topics: Two pointers, Array
Solved: No attempts yet

Problem

Consider an $N$ -element strictly increasing integer sequence $A$ and an integer $S$ .

Write a program to count the number of pairs of elements of $A$ whose sum is $S$ .

Input

The first line contains $N$ and $S$ , the length of the sequence and the required sum ( $1 \le N \le 100\,000$ , $0 \le S \le 2\,000\,000$ ). The following $N$ lines each contain one element $A_i$ ( $0 \le A_i \le 1\,000\,000$ ). The elements are distinct and sorted in increasing order.

Output

The only line of output contains the number of pairs of two distinct elements of the sequence whose sum is $S$ .

Examples1

Example 1
Input
```
5 10
1
3
5
7
9
```
Expected output
```
2
```