도로 공사

남규는 술을 좋아해서 매일 술을 마신다. 남규의 주사는 특이하게도 도로 공사다.

남규가 술을 마시고 집으로 돌아가는 길은 직진만 되는 일방통행이고, 높이가 서로 다른 $N$개의 구간으로 나뉜다. 즉 남규가 집으로 가면서 지나는 길의 높이를 순서대로 정수 $N$개로 적을 수 있다.

남규는 술을 마신 날마다 집에 가는 도중에 구간 하나를 정하고, 그 시작 위치부터 끝 위치까지 높이의 순서가 뒤집히도록 공사한다. 예를 들어 길이가 5인 길의 높이가 순서대로 1 2 3 4 5라고 하자. 2번 위치에서 시작해 4번 위치에서 끝나는 구간을 공사하면 높이는 1 4 3 2 5가 된다.

남규에게도 양심이 있어서, 술을 마신 다음 날에는 일어나자마자 어제 공사한 구간으로 가 길을 원래 모습으로 되돌려 놓는다.

남규와 매일 함께 술을 마시는 재혁이는 이 광경을 옆에서 지켜보다가, 길이 바뀔 때마다 길 전체에 오르막길이 몇 개인지 궁금해졌다. 재혁이를 위해 오르막길의 개수를 세어 주자.

오르막길은 높이가 계속 증가하는 연속된 구간이다. $i$번 위치의 높이보다 $i+1$번 위치의 높이가 크면 두 위치는 반드시 같은 오르막길에 속한다. 오르막길은 더 늘릴 수 없을 때까지 길게 잡으므로 모든 위치가 정확히 하나의 오르막길에 들어가고, 길이가 1인 구간도 오르막길 하나로 센다.

첫째 줄에 도로의 길이 $N$과 재혁이가 지켜본 기간 $M$이 주어진다. ($1 \le N, M \le 10^5$)

둘째 줄에 각 위치의 높이를 뜻하는 정수 $a_i$가 $N$개 주어진다. ($1 \le a_i \le 10^9$)

다음 $M$개의 줄에는 $i$번째 날에 공사한 구간을 뜻하는 $l_i$와 $r_i$가 주어진다. ($1 \le l_i \le r_i \le N$)

모든 위치의 번호는 1부터 시작하고, 높이가 같은 두 위치는 없다.

$M$개의 줄에 걸쳐 각 날의 공사가 끝난 뒤 길 전체의 오르막길 개수를 출력한다.

공사는 누적되지 않는다. 각 공사는 처음 길 상태에 독립적으로 적용된다.