Problem Description

Given an integer sequence of length $N$, $A_1, A_2, \ldots, A_N$, and an integer $X$, count the number of tuples $(l, m, r)$ that satisfy all of the following conditions:

• $1 \le l \le m \le r \le N$
• $A_l + A_m + A_r = X$
• $A_m$ is the maximum value of $A_i$ for $l \le i \le r$

Input Format

The input is given from the standard input in the following format:

$N\ X$ $A_1\ A_2\ \ldots\ A_N$

Output Format

Output the number of tuples that satisfy the conditions in one line.

Sample Input and Output

Sample Input #1

6 9
1 2 4 4 3 2

Sample Output #1

6

Sample Input #2

3 0
0 0 0

Sample Output #2

10

Sample Input #3

10 15
3 1 4 1 5 9 2 6 5 3

Sample Output #3

7

Notes/Hints

Constraints

• $1 \le N \le 10^5$
• $0 \le X \le 3 \times 10^5$
• $0 \le A_i \le 10^5$
• All inputs are integers

Partial Points

This problem has partial points.

• Correctly solving for inputs where $N \le 2000$ will award $300$ points.

Sample Explanation 1

The $6$ tuples are $(l, m, r) = (1, 3, 3), (1, 3, 4), (1, 4, 4), (2, 3, 5), (2, 4, 5), (5, 5, 5)$.

见题面 Input 部分

见题面 Output 部分