## DeMello's Leeches

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

After starting his class with students , 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 to , which adds layer of salt to each student from .

Initially, each student has a salt tolerability : 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 , the number of students in the class.

The next line will contain integers , the salt tolerability of the student.

The next line will contain , the number of salt layers that will be applied.

The next lines will contain integers and , 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.

#### 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, is discovered as a leech because they have received layers of salt . After the third salt range, is discovered as a leech because they have received layers of salt. After the fourth salt range, is discovered as a leech because they have received layers of salt. After the fifth salt range, is discovered as a leech because they have received 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