Problem B: Counting Triples

Problem B: Counting Triples

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 3825  Solved: 522
[Submit][Status][Web Board]


There is an array \(a_1, a_2, ..., a_n\). Do you know how many triples \((i,j,k)\) are there, which satisfy that \(i<j<k\) and \(a_i+a_j+a_k=S\) ?


The first line contains two integers \(n (1\leq n\leq 3*10^3), S (1\leq S\leq 10^9)\), indicating the length of the array and the sum of three elements for each triple.

The second line contains \(n\) integers \(a_1, a_2, ... a_n (1\leq a_i\leq 10^9)\), indicating the array. It's guaranteed that the array is non-decreasing.


Output the answer in one line.

Sample Input

5 700
100 200 200 300 300

Sample Output