히스토그램과 쿼리

너비가 $1$이고 높이가 $a_1, a_2, \cdots, a_N$인 $N$개의 직사각형이 주어진다. 각 직사각형은 주어지는 순서대로 $1$부터 $N$까지의 번호가 붙어 있으며, $i$번 직사각형의 높이는 $a_i$이다.

주어진 직사각형들을 순서대로 이어 붙이면 히스토그램이 만들어진다. 당신은 히스토그램을 다음 조건에 따라 직사각형 모양으로 덮을 수 있다.

• 직사각형은 가로 길이와 세로 길이가 모두 $1$ 이상인 정수이다.
• 직사각형들 사이에는 겹침이 있어서는 안 된다.
• 직사각형이 히스토그램의 영역 바깥을 덮어서는 안 된다.
• 히스토그램의 모든 부분이 직사각형에 의해 덮여야 한다.

$Q$개의 쿼리가 주어진다. 각 쿼리는 두 정수 $l_j, r_j$로 구성되어 있으며, $l_j$번부터 $r_j$번까지의 직사각형을 순서대로 이어 붙여 만든 히스토그램을 덮기 위해 최소 몇 개의 직사각형이 필요한지 구해야 한다.

첫째 줄에 히스토그램을 구성하는 직사각형의 개수 $N$이 주어진다. ($1 \le N \le 10^6$)

둘째 줄에 $N$개의 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. ($1 \le a_i \le N$)

셋째 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 10^6$)

다음 $Q$개의 줄에는 두 개의 정수 $l_j, r_j$가 공백으로 구분되어 주어진다. ($1 \le l_j \le r_j \le N$)

$Q$개의 줄에 걸쳐 각 쿼리의 답을 한 줄에 하나씩 출력한다.