Problem Description

You are given a list of integers and a target value. Your task is to count how many unique pairs of numbers in the list sum up exactly to the target value.

Important Notes:

• A pair consists of two different elements at different positions in the list
• We count distinct value pairs, not distinct index pairs
• The order within a pair doesn't matter: (a, b) is the same as (b, a)
• We only count pairs where i < j (to avoid duplicates)

Input Format

• First line: An integer n (1 ≤ n ≤ 100,000) — the number of integers in the list
• Second line: n integers a₁, a₂, ..., aₙ (-10⁹ ≤ aᵢ ≤ 10⁹)
• Third line: An integer t (-2×10⁹ ≤ t ≤ 2×10⁹) — the target sum

Output Format

• A single integer — the number of distinct pairs (a, b) such that a + b = t and the elements come from different positions with i < j

Examples

Example 1

Input:

5
1 3 2 2 4
4

Output:

2

Explanation: The pairs that sum to 4 are:

• (1, 3)
• (2, 2)

Example 2

Input:

6
1 1 1 1 1 1
2

Output:

1

Explanation: Only one distinct pair: (1, 1)

Example 3

Input:

4
1 2 3 4
10

Output:

0

Explanation: No pairs sum to 10

Constraints

• Large input size: up to 100,000 elements
• Large value range: numbers can be very large (up to ±10⁹)
• Need efficient O(n) or O(n log n) solution

Solution Approach

This problem can be efficiently solved using a hash map (dictionary) to track the frequency of numbers we've seen so far. For each number x in the array, we check if t - x exists in our frequency map. If it does, we've found valid pairs.

Key Insight:

• If x ≠ t - x, then the number of pairs is freq[t - x]
• If x = t - x, then the number of pairs is the combination C(freq[x], 2)

We process numbers in order and use the frequency map to avoid double-counting while ensuring we only count each distinct pair once.