Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

City of Burgerland

By emrul_mu · Limits 1s, 256 MB

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 N number of burger shops. The shops are numbered from 11 to NN. The ithi^{th} shop has the capacity to serve Bi 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 M queries, in each query, the mayor will give you three integers l,r and cap l, r \text{ and } cap . He wants to know the minimum number of capacity needed to be increased so that every shop numbered between ll to rr have serving capacity at least capcap.

Suppose, there are 44 burger shops having capacity [1,7,3,5][1, 7, 3, 5]. If the mayor gave you l=2,r=4 l = 2, r = 4 and cap=6 cap = 6 , then the answer is 44 as it is needed to be increased the capacity of 3rd3^{rd} shop by 33 and the capacity of 4th4^{th} shop by 11 to make all the shops between segment (2,4)(2, 4) having capacity at least 66. As the 2nd2^{nd} burger shop has the capacity equal to 77 which is more than 66, no need to increase it.

Input

The first line of input contains two integers N(1N105) and M(1M5×105)N (1 ≤ N ≤ 10^{5}) \text{ and } M (1 ≤ M ≤ 5 \times 10^{5}).

The second line contains NN integers, the ithi^{th} integer denotes Bi(1Bi109)B_{i} (1 ≤ B_{i} ≤ 10^{9}) which is the capacity of production of the ithi^{th} burger shop.

Each of the next MM lines contains l,r and cap (1lrN,1cap109)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(Bl,Bl+1,..,Br)min(B_{l}, B_{l + 1},.., B_{r}) will be at least cap cap in separate lines.

Sample

InputOutput
4 1
1 7 3 5
2 4 6
4

Discussion

Statistics


56% Solution Ratio

tmwilliamlin168Earliest, Jan '20

Sobi777Fastest, 0.2s

insane_curiousLightest, 9.2 MB

tmwilliamlin168Shortest, 964B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.