Asilbek has an array \(A\) of length \(N\) and a number \(T\). Among all intervals \(1 \le l \le r \le N\), he wants to count those satisfying \(F(l, r) \le T\). Help him.
\(F(l, r)\) is computed as follows:
– Let \(B_1 = A_l;\ B_2 = A_{l+1};\ \dots;\ B_{r-l+1} = A_r\).
– In one operation, any element of \(B\) may be increased or decreased by 1.
– \(F(l, r)\) equals the minimum number of operations needed to make all elements of \(B\) equal.
For example, let \(A = [4, 2, 8, 5]\). Then \(F(1, 2) = 2\), \(F(3, 3) = 0\), and \(F(1, 4) = 7\).
The first line contains two integers – \(N\) and \(T\) (\(1 \le N \le 5 \cdot 10^5\); \(0 \le T \le 5 \cdot 10^{14}\)).
The second line contains \(N\) integers – the elements of the array \(A\) (\(0 \le A_i \le 10^9\)).
For the given array \(A\), print the number of pairs \(1 \le l \le r \le N\) satisfying \(F(l, r) \le T\).
4 3 4 2 8 5
6
4 0 1 1 1 1
10
In the first test, the following intervals satisfy the condition: \([1, 1]\); \([2, 2]\); \([3, 3]\); \([4, 4]\); \([1, 2]\) and \([3, 4]\).