Pairs with a given sum

Problem

Count the pairs of positions i < j whose items add up to the target. Equal values at different positions count as different pairs.

Example

Input

5 6
1 5 7 -1 5

Output

Pairs: 1+5, 1+5 (the other 5) and 7+(-1).

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

Hint 1

For each item, count how many earlier items equal target - item.

Hint 2

A Counter updated after the lookup does this in one pass.

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