Have you ever heard of The Burgerland City? The city is full of burger shops. You will surely find some shops of burgers wherever you will look around to any part of that city.
The Burgerland consists of $ N $ number of burger shops. The shops are numbered from $1$ to $N$. The $i^{th}$ shop has the capacity to serve $ B_{i} $ burgers daily. The mayor of the city wants some consecutive shops to have at least a specific serving capacity to make the city more attractive to the visitors. You are recruited as a programmer to help the mayor in this project by answering some queries.
The mayor wants to ask $ M $ queries, in each query, the mayor will give you three integers $ l, r \text{ and } cap $. He wants to know the minimum number of capacity needed to be increased so that every shop numbered between $l$ to $r$ have serving capacity at least $cap$.
Suppose, there are $4$ burger shops having capacity $[1, 7, 3, 5]$. If the mayor gave you $ l = 2, r = 4 $ and $ cap = 6 $, then the answer is $4$ as it is needed to be increased the capacity of $3^{rd}$ shop by $3$ and the capacity of $4^{th}$ shop by $1$ to make all the shops between segment $(2, 4)$ having capacity at least $6$. As the $2^{nd}$ burger shop has the capacity equal to $7$ which is more than $6$, no need to increase it.
Input
The first line of input contains two integers $N (1 ≤ N ≤ 10^{5}) \text{ and } M (1 ≤ M ≤ 5 \times 10^{5})$.
The second line contains $N$ integers, the $i^{th}$ integer denotes $B_{i} (1 ≤ B_{i} ≤ 10^{9})$ which is the capacity of production of the $i^{th}$ burger shop.
Each of the next $M$ lines contains $l, r \text{ and } cap\text{ }(1 ≤ l ≤ r ≤ N, 1 ≤ cap ≤ 10^{9})$.
Output
For each query, print the minimum number of capacity is needed to be increased so that $min(B_{l}, B_{l + 1},.., B_{r}) $ will be at least $ cap $ in separate lines.
Sample
| Input | Output |
|---|---|
4 1 1 7 3 5 2 4 6 | 4 |
