15670번 - 도로 공사

남규는 술을 좋아해 매일 술을 마신다. 남규의 주사는 특이하게도 도로공사이다. 억지처럼 느껴진다면 어쩔 수 없다.

남규가 술을 마신 뒤 집에 돌아가는 길은 직진만 가능한 일방통행 길이며, N개의 높이가 서로 다른 구간으로 나눌 수 있다. 즉, 정수 N개로 남규가 집에 가는 길에 마주치는 길의 높이를 순서대로 적을 수가 있다.

남규는 술을 마신 날마다, 집에 가는 도중에 특정 구간(시작 위치와 끝 위치)을 정해서 높이가 기존의 역방향이 되도록 공사를 한다. 예를 들어, 집에 가는 경로를 N=5개의 구간으로 나누어 높이를 측정했다고 하자. 아래는 지속해서 높이가 증가하는 길의 예제이다.

1 2 3 4 5

이 상태에서, 2번 위치에서 시작해 4번 위치에서 끝나는 구간에 대해 도로공사를 하면 길의 상태는 아래와 같이 바뀐다.

1 4 3 2 5

남규에게도 양심이 있기 때문에, 술을 마신 다음날에는 항상 일어나자마자 다시 어제 공사했던 구간으로 가 재빠르게 원래 모습으로 복원해놓는다.

남규와 술을 매일 같이 먹는 재혁이는 매일 이러한 일을 옆에서 지켜봐 왔고, 어느 날부터인가 길이 바뀔 때마다 길 전체에 대해 오르막길이 몇 개가 되는지 궁금해졌다. 재혁이를 위해 오르막길의 개수를 세어 주자.

오르막길이란, 높이가 점점 증가하는 연속된 구간을 의미하며, 만일 i번 위치의 높이보다 i+1번 위치의 높이가 크다면 그 둘은 반드시 같은 오르막길에 속해야 한다.

첫째 줄에 도로의 길이 N, 재혁이가 관찰한 기간 M이 주어진다. (1 ≤ N, M ≤ 10⁵)

둘째 줄에 각 지점의 높이를 의미하는 N개의 숫자 a_i가 주어진다. (1 ≤ a_i ≤ 10⁹)

다음 M개의 줄에 i번째 날에 공사한 구간을 의미하는 l_i, r_i(1 ≤ l_i ≤ r_i ≤ N)가 주어진다.

모든 인덱스는 1부터 시작하며, 어떤 두 구간의 높이가 같은 경우는 없다.

M줄에 걸쳐, 각 날마다 바뀐 전체 도로에서의 오르막길의 개수를 출력한다.

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