Triangles and a Circle

Time limit1sMemory limit512 MB

Summary

Count triangles formed by n points on a circle of circumference L whose interior or border contains the circle's center.

Level: Medium7 of 10
Topics: Two pointers, Combinatorics, Geometry, Sorting
Solved: No attempts yet

Problem

You are given $n$ distinct points on a circle of length $L$ .

Find the number of triangles with vertices at these points that contain the center of the circle inside or on their border.

Input

The first line contains two integers $n$ and $L$ ( $3 \leq n \leq 300\,000$ , $n \leq L \leq 10^9$ ).

Pick any point on the circle and call it $S$ . Then any point $A$ on the circle can be written as $x$ with $0 \le x < L$ , the clockwise distance from $S$ to $A$ . We call this number the coordinate of $A$ .

The second line contains $n$ distinct integers $x\_1, x\_2, \ldots, x\_n$ , the coordinates of the given points ( $0 \leq x\_i < L$ ).

Output

Print one integer: the number of triangles with vertices at the given points that contain the center of the circle inside or on their border.

Examples2

Example 1
Input
```
3 10
0 1 2
```
Expected output
```
0
```
Example 2
Input
```
10 10
0 1 2 3 4 5 6 7 8 9
```
Expected output
```
60
```