Two turnstiles at a venue each stamp a signed integer offset on every entry, and the log lists n such offsets in the order they were recorded. Management wants to know how many pairs of distinct log entries have offsets that add up to exactly a target value t.
Count the number of unordered pairs of positions (i, j) with i < j such that entry[i] + entry[j] == t. The log is not sorted, and values may repeat or be negative.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the offsets in recorded order.
Line 3: an integer t, the target sum.
Output format
A single integer: the number of unordered index pairs whose offsets sum to t.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ each offset ≤ 1000000000
- -2000000000 ≤ t ≤ 2000000000