Count pairs with a target total

Problem

Given n integers and a target, count the pairs of positions i < j whose values add up to the target. Checking every pair is too slow.

Example

Input

7 8
1 5 3 3 7 5 1

Output

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

Hint 1

A pair loop is O(n²). For each value, what partner value would complete the total?

Hint 2

Keep a Counter of values already seen. Before adding a value, add how many times its partner was seen.

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