오래전, 미노타우르스가 갇혀 있던 거대한 미궁에는 수많은 봉인석이 일렬로 놓인 통로들이 존재했다.

라이즈는 미궁의 중심부로 향하기 위해 여러 통로를 조사하고 있다.
각 통로에는 1번부터 \(N\)번까지 번호가 붙은 봉인석이 일렬로 놓여 있으며, \(i\)번 봉인석의 마력 높이는 \(H_i\)이다.

라이즈는 어떤 구간 \([l, r]\)의 통로를 조사할 때, \(l\)번 봉인석의 왼쪽에서 오른쪽 방향으로 마법의 빛을 쏜다.

마법의 빛은 다음 규칙에 따라 봉인석에 닿는다.

첫 번째 봉인석 \(l\)은 항상 빛을 받는다.

그 이후의 봉인석 \(i\)는, 구간 \([l, i-1]\)에 있는 모든 봉인석보다 마력 높이가 클 때만 빛을 받는다.

즉, 라이즈가 왼쪽에서 오른쪽으로 바라볼 때, 지금까지 본 모든 봉인석보다 더 높은 봉인석만 빛을 받는다.

라이즈는 \(Q\)개의 통로 구간을 조사하려고 한다.
각 조사마다 구간 \([l, r]\)에서 마법의 빛을 받는 봉인석의 개수를 구하시오.

\(1 ≤ N ≤ 200\,000\)
\(1 ≤ Q ≤ 200\,000\)
\(1 ≤ H_i ≤ 1\,000\,000\,000\)
\(1 ≤ l ≤ r ≤ N\)

첫째 줄에 봉인석의 개수 \(N\)과 조사 횟수 \(Q\)가 주어진다.

둘째 줄에 각 봉인석의 마력 높이 \(H_1, H_2, \dots, H_N\)이 공백으로 구분되어 주어진다.

셋째 줄부터 \(Q\)개의 줄에 걸쳐 두 정수 \(l, r\)이 주어진다.

각 조사마다 구간 \([l, r]\)에서 마법의 빛을 받는 봉인석의 개수를 한 줄에 하나씩 출력한다.

anthony0506 작성

출처 anthony0506