You are given an integer array a of length n and an integer target. Count the number of pairs of positions (i, j) with i < j such that a[i] + a[j] == target.
Equal values at different positions are counted as distinct pairs — for example, in [0, 0, 0] with target 0 there are three valid pairs of positions.
Input format
Line 1: two integers n and target, separated by a space.
Line 2: n space-separated integers a[0] … a[n-1]. If n == 0, this line is empty or absent.
Output format
A single integer: the number of position pairs (i, j) with i < j and a[i] + a[j] == target.
Constraints
- 0 ≤ n ≤ 100000
- -1000000000 ≤ target ≤ 1000000000
- -1000000000 ≤ a[i] ≤ 1000000000
- The answer can be large; it fits in a 64-bit signed integer.