zatopljenje — COCI CONTEST_#2
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 16
Algorithms: line sweep, range queries, offline queries, binary indexed tree

## Task Zatopljenje

**Task**: Zatopljenje

**Time Limit**: 2 seconds

**Memory Limit**: 512 MiB

**Points**: 110

It's winter, it has never been colder, and Mr. Malnar is looking at his photos from his last cruise on the Adriatic and recalls unforgettable moments. The TV is on in the background, broadcasting news about the latest proposals for measures to slow down sea level rise. Looking at his photos of the coast, Mr. Malnar asks himself what the photos would have looked like if sea level had risen a certain amount. There are so many pictures, and even more questions, so Mr. Malnar asks for your help.

![Coastline Image](./_page_0_Picture_4.jpeg)

We imagine the coast as a sequence of *n* numbers *h*<sub>1</sub>, *h*<sub>2</sub>, ..., *h*<sub>n</sub>, where the *i*-th number represents the relief height at the *i*-th point. Mr. Malnar has *q* queries, where the *i*-th query is as follows: How many islands would there be between the *l*<sub>i</sub>-th and *r*<sub>i</sub>-th point if the sea level rose by *x*<sub>i</sub> meters?

![Island Examples](./_page_0_Figure_6.jpeg)

*The left image shows the first query of the first sample test case, and the right image shows the second query of the second sample test case.*

*The left islands correspond to intervals [2, 2] and [4, 5]. The right islands correspond to intervals [1, 1], [4, 4], [8, 8] and [10, 10].*

An island is defined as the maximal interval where every *h*<sub>i</sub> is **strictly** greater than the sea level. A maximal interval is one that cannot be extended in either direction while keeping the mentioned condition true. Initially, the sea level is at 0 meters.

## Input

The first line contains integers *n* and *q* (1 ≤ *n*, *q* ≤ 2 ⋅ 10<sup>5</sup>), representing the length of the sequence and the number of queries.

The second line contains *n* integers *h*<sub>1</sub>, *h*<sub>2</sub>, ..., *h*<sub>n</sub> (0 ≤ *h*<sub>i</sub> ≤ 10<sup>9</sup>) that describe the relief of the coast.

In each of the next *q* lines, there are three integers *l*<sub>i</sub>, *r*<sub>i</sub>, and *x*<sub>i</sub> (1 ≤ *l*<sub>i</sub> ≤ *r*<sub>i</sub> ≤ *n*, 0 ≤ *x*<sub>i</sub> ≤ 10<sup>9</sup>) that describe the *i*-th query.

## Output

In the *i*-th of the *q* lines, print the answer to the *i*-th query. Each of the queries is independent of the others.

![Page Break](./_page_1_Picture_0.jpeg)

## Scoring

| Subtask | Points | Constraints                                                                                                                                  |
| :-------: | :----: | :------------------------------------------------------------------------------------------------------------------------------------------- |
|     1     |   10   | *n*, *q* ≤ 2 ⋅ 10<sup>3</sup>                                                                                                             |
|     2     |   20   | *l*<sub>i</sub> = 1, *r*<sub>i</sub> = *n* for all *i* = 1, 2, ..., *q*                                                                       |
|     3     |   20   | There exists an integer *p* (1 ≤ *p* < *n*) such that:  *h*<sub>1</sub> ≥ *h*<sub>2</sub> ≥ ... ≥ *h*<sub>p</sub> ≤ *h*<sub>p+1</sub> ≤ ... ≤ *h*<sub>n</sub> |
|     4     |   60   | No additional constraints                                                                                                                |

## Examples

| Input                                 | Input                                   |
| :------------------------------------ | :-------------------------------------- |
| 6 3                                   | 10 3                                  |
| 2 4 2 3 4 1                             | 5 0 3 4 2 0 1 6 3 5                     |
| 2 5 2                                 | 3 9 1                                 |
| 3 5 3                                 | 1 10 3                                |
| 3 4 4                                 | 1 10 2                                |
| Output                                | Output                                  |
| 2                                     | 2                                     |
| 1                                     | 4                                     |
| 0                                     | 3                                     |

**Clarification of the first example:**

The first query is shown in the left image in the task description; islands correspond to intervals [2, 2] and [4, 5]. In the second query, the island corresponds to interval [5, 5]. In the third query, there are no islands because everything is underwater.

**Clarification of the second example:**

In the first query, islands correspond to intervals [3, 5] and [8, 9]. In the second query (shown in the right image in the task description), islands correspond to intervals [1, 1], [4, 4], [8, 8], and [10, 10], while in the third query islands correspond to intervals [1, 1], [3, 4], and [8, 10].

Starter code: