Jumong's Armor Materials

Interview

Time limit2sMemory limit128 MB

Summary
Count how many pairs of given numbers sum to a target value M, using each material at most once per pair.
Level

Easy3 of 10

Topics
Two pointers, Array, Sorting
Solved
No attempts yet

Problem

Jumong is preparing armor for an iron army. Each material has a distinct identifier.

One piece of armor can be made from two materials. If the sum of the two identifiers is M, those two materials can be used to make one piece of armor.

Given N material identifiers and the target value M, determine how many pieces of armor can be made.

Input

The first line contains the number of materials N. (1 <= N <= 15,000)

The second line contains the required identifier sum M. (1 <= M <= 10,000,000)

The third line contains N material identifiers separated by spaces. Each identifier is a natural number at most 100,000.

Output

Print the number of pieces of armor that can be made.

Examples1

  1. Example 1

    Input
    6
9
2 7 4 1 5 3
    Expected output
    2