Pairs with a given sum

Problem

Count the pairs of positions i < j whose values add up to a target. Equal values at different positions are different pairs. The starter holds a program with a bug. Find it and fix it.

Input, output and limits

Input: Line 1: n and target. Line 2: n integers.
Output: One integer: the number of pairs.
Constraints: 1 ≤ n ≤ 100000
-1000 ≤ each value, target ≤ 1000

Examples

Example

Input

4 6
3 3 3 3

Output

Every two of the four threes make a pair: 6 pairs.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Walk through the list and keep a count of every value seen before.

Hint 2

For each x, the pairs it completes equal the count of target - x so far.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Best stretch of markshard
Longest run of equal valueshard
Find each valuemedium
Merge booking timeshard
Balanced bracketsmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems