Road Construction

Namgyu likes to drink and drinks every day. His drunken habit is an unusual one: road construction.

The road Namgyu walks home after drinking is one way and only goes forward, and it splits into $N$ sections whose heights are all different. The heights he meets on the way home can be written down in order as $N$ integers.

On every day he drinks, Namgyu picks one part of the road on his way home, a start position and an end position, and rebuilds it so that the heights between them come out in reverse order. Suppose a road of length 5 has heights 1 2 3 4 5 in order. Rebuilding the part that starts at position 2 and ends at position 4 turns the heights into 1 4 3 2 5.

Namgyu has a conscience, so the day after he drinks he gets up, walks back to the part he rebuilt, and restores it to its original shape.

Jaehyuk drinks with Namgyu every day and has watched all of this from the side. He wants to know how many uphill roads the whole road has each time the road changes. Count the uphill roads for him.

An uphill road is a run of consecutive positions whose heights keep increasing. If the height at position $i+1$ is greater than the height at position $i$, the two positions belong to the same uphill road. Every uphill road is taken as long as it can be, so each position falls into exactly one uphill road, and a run of a single position counts as one uphill road.

The first line contains the length of the road $N$ and the number of days Jaehyuk watched, $M$. ($1 \le N, M \le 10^5$)

The second line contains $N$ integers $a_i$, the height of each position. ($1 \le a_i \le 10^9$)

Each of the next $M$ lines contains $l_i$ and $r_i$, the part rebuilt on day $i$. ($1 \le l_i \le r_i \le N$)

Positions are numbered from 1, and no two positions have the same height.

Print $M$ lines. On line $i$, print the number of uphill roads on the whole road after the construction of day $i$.

The construction does not pile up. Each day's construction applies to the original road independently.