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 is an integer \(P > 1\) which is only divisible by \(1\) and \(P\) . For example, \(2\) , \(3\) , \(5\) , \(7\) , \(11\) are the first few primes, and \(4\) , \(6\) , \(8\) , \(9\) are not prime numbers.

  Input Specification

  The first line of input is the number \(T\) \((1 \le T \le 1\,000)\) , which is the number of test cases. Each of the next \(T\) lines contain one integer \(N_i\) \((4 \le N_i \le 1\,000\,000, 1 \le i \le T)\) .

  For 6 of the available 15 marks, all \(N_i < 1\,000\) .

  Output Specification

  The output will consist of \(T\) lines. The \(i^\text{th}\) line of output will contain two integers, \(A_i\) and \(B_i\) , separated by one space. It should be the case that \(N_i=\dfrac{A_i + B_i}{2}\) and that \(A_i\) and \(B_i\) are prime numbers.

  If there are more than one possible \(A_i\) and \(B_i\) for a particular \(N_i\) , output any such pair. The order of the pair \(A_i\) and \(B_i\) does not matter.

  It will be the case that there will always be at least one set of values \(A_i\) and \(B_i\) for any given \(N_i\) .

  Sample Input

  4
  8
  4
  7
  21

  Sample Output

  3 13
  5 3
  7 7
  13 29

  Explanation of Possible Output for Sample Input

  Notice that:

  \[\displaystyle \begin{align} 8 &= \frac{3 + 13}{2}, \\ 4 &= \frac{5 + 3}{2}, \\ 7 &= \frac{7 + 7}{2}, \\ 21 &= \frac{13 + 29}{2}. \end{align}\]

  It is interesting to note, that we can also write

  \[\displaystyle \begin{align} 8 &= \frac{5 + 11}{2} \\ 21 &= \frac{5 + 37}{2} = \frac{11 + 31}{2} = \frac{19 + 23}{2} \\ 7 &= \frac{3 + 11}{2} \end{align}\]

  and so any of these pairs could have also been used in output. There is no pairs of primes other than \(3\) and \(5\) which average to the value of \(4\) .

  Footnote

  You may have heard about Goldbach's conjecture , which states that every even integer greater than 2 can be expressed as the sum of two prime numbers. There is no known proof, yet, so if you want to be famous, prove that conjecture (after you finish the CCC).

  This problem can be used to help verify that conjecture, since every even integer can be written as \(2N\) , and your task is to find two primes \(A\) and \(B\) such that \(2N = A + B\) .

  , then the number of pairs is the combination C(freq[x], 2)