Sum of Two Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Count pairs of distinct integers in an array that sum exactly to a given value x.

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

Problem

You are given a sequence of $n$ distinct positive integers $a_1, a_2, \dots, a_n$ , where each $a_i$ is a natural number with $1 \le a_i \le 1\,000\,000$ .

Given a natural number $x$ , write a program that counts the number of pairs $(a_i, a_j)$ with $1 \le i < j \le n$ such that $a_i + a_j = x$ .

Input

The first line contains the size of the sequence, $n$ .

The second line contains the $n$ distinct natural numbers of the sequence, separated by spaces.

The third line contains the natural number $x$ .

$1 \le n \le 100\,000$ , $1 \le a_i \le 1\,000\,000$ , $1 \le x \le 2\,000\,000$

Output

Print the number of pairs that satisfy the condition on a single line.

Examples7

Example 1
Input
```
9
5 12 7 10 9 1 2 3 11
13
```
Expected output
```
3
```
Example 2
Input
```
1
5
10
```
Expected output
```
0
```
Example 3
Input
```
2
1 2
3
```
Expected output
```
1
```
Example 4
Input
```
3
1 2 3
100
```
Expected output
```
0
```
Example 5
Input
```
5
2 3 5 7 8
10
```
Expected output
```
2
```
Example 6
Input
```
6
1 2 3 4 5 6
7
```
Expected output
```
3
```
Example 7
Input
```
2
1 1000000
1000001
```
Expected output
```
1
```