Counting the number of intervals
/

## Advanced Data Structures, Data Structures, Segment tree

Problem
Editorial
Analytics

You are given a sequence of $N$ integers $a_1, a_2, \dots, a_N$ and an integer $K$. Your task is to count the number of intervals $[l, r]$ such that $a_l + a_r + min(a_l, a_{l + 1}, \dots, a_r) \le K$.

Input format

• First line: Two space-separated integers $N, K$
• Second line: $N$ space-separated integers denoting the elements of the sequence

Output format

• Print the answer in a single line.

Constraints

$1 \le N \le 5\times10^5$,  $80\%$ test cases $N \le 2\times 10^5$

$1 \le K \le 10^{18}$

$1 \le a_i \le 10^{18}$

SAMPLE INPUT
5 6
1 2 3 4 5

SAMPLE OUTPUT
5
Explanation

There are five intervals satisfy the condition:

• [1, 1]: $a_1 + min(a_1) + a_1 = 3$
• [1, 2]: $a_1 + min(a_1, a_2) + a_2 = 4$
• [1, 3]: $a_1 + min(a_1, a_2, a_3) + a_3 = 5$
• [1, 4]: $a_1 + min(a_1, a_2, a_3, a_4) + a_4 = 6$
• [2, 2]: $a_2 + min(a_2, a_2) + a_2 = 6$
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...