Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hablu's Team

By shihan04 · Limits 1s, 512 MB

This year Hablu wants to participate in ICPC. He studies in “Habagoba University” along with nn other students. Everyone in the University has a “Problem solving skill level”. Hablu needs 2 other members to make a team.

But Hablu is really dumb! He will select two students if and only if the summation of their “Problem solving skill level”s is less than his own (What?)!

Now your task is to calculate how many ways Hablu can make his team. Two teams are considered different if a student xx is on the first team but not on the second one.

Input

In the first line you will be given two integers nn and kk (1n,k1051 \leq n, k \leq 10^5) representing the number of students other than Hablu and Hablu's “Problem solving skill level” respectively. Next line will contain nn integers aia_i (1ai1051 \leq a_i \leq 10^5) — the “Problem solving skill level”s of other students.

Output

Output a single integer — the number of ways Hablu can make his team.

Samples

InputOutput
4 10
1 1 2 7
6
InputOutput
5 1
1 2 3 4 5
0

Output may not fit into 32 bit integer. Use 64 bit integer.

Discussion

Statistics


67% Solution Ratio

nuipqiunEarliest, Apr '20

md_jakariyaFastest, 0.0s

Lazy_ProgrammerLightest, 131 kB

mdvirusShortest, 169B

Submit

Login to submit

Editorial

You can just do binary search and solve it in O(nlogn)O(nlogn)O(nlogn) time complexity. #include<...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.