After starting his class with ~n~ students ~(1 \le n \le 200\,000)~, DeMello wants to first get rid of all the leeches in his class!

To get rid of these leeches, DeMello will apply salt on ranges of ~L~ to ~R~ ~(1 \le L \le R \le n)~, which adds ~1~ layer of salt to each student from ~[L, R]~.

Initially, each student has a salt tolerability ~(0 \le S_i \le n)~: when a student has more salt than their salt tolerability, they will shrivel up and be marked as a leech.

After applying each range of salt, DeMello wants to know how many new leeches were discovered.

Help DeMello find all the leeches!

Input Specification

The first line of input will contain ~n~ ~(1 \le n \le 200\,000)~, the number of students in the class.

The next line will contain ~n~ integers ~(0 \le S_i \le n)~, the salt tolerability of the ~i^\text{th}~ student.

The next line will contain ~Q~ ~(1 \le Q \le 200\,000)~, the number of salt layers that will be applied.

The next ~Q~ lines will contain ~2~ integers ~L~ and ~R~ ~(1 \le L \le R \le n)~, the left and right index of each range of salt.

Output Specification

For each layer of salt added, output the new number of leeches discovered.

Constraints

For all subtasks:

~1 \le n \le 200\,000~

~0 \le S_i \le n~

~1 \le Q \le 200\,000~

Subtask 1 [30%]

~Q = 1~

Subtask 2 [70%]

No additional constraints.

Sample Input 1

5
1 2 3 4 5
5
1 5
1 5
1 5
1 5
1 5

Sample Output 1

0
1
1
1
1

Explanation for Sample Output 1

After the first salt range, no new leeches are discovered. After the second salt range, ~1~ is discovered as a leech because they have received ~2~ layers of salt ~(2 > S_1)~. After the third salt range, ~2~ is discovered as a leech because they have received ~3~ layers of salt. After the fourth salt range, ~3~ is discovered as a leech because they have received ~4~ layers of salt. After the fifth salt range, ~4~ is discovered as a leech because they have received ~5~ layers of salt.

Sample Input 2

6
0 3 0 4 2 2
5
1 3
1 6
1 6
1 6
1 1

Sample Output 2

2
0
0
3
0