Count Pairs with a Given Sum

You are given an array of integers and a target integer \(S\). Your task is to find the number of distinct pairs \((i, j)\) (with \(i < j\)) such that the sum of the corresponding elements is exactly \(S\). In other words, you need to count the number of pairs \((a_i, a_j)\) where:

[ a_i + a_j = S ]

When both numbers in the pair are identical, they can form a valid pair as long as there are at least two occurrences. The number of ways to choose 2 out of \(n\) identical elements is given by the formula:

[ \binom{n}{2} = \frac{n(n-1)}{2} ]

Please note that each pair is counted only once.

inputFormat

The input is read from the standard input (stdin) and has the following format:

• The first line contains a single integer \(n\) — the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements.
• The third line contains a single integer \(S\) — the target sum.

outputFormat

Output a single integer to the standard output (stdout), which is the number of distinct pairs that sum up to \(S\).

4
1 5 7 1
6

2