The Staging

Memory limit: 256 MB

Steven Byteberg is a movie director, specialising in action movies. Presently he is working on a new movie, whose theme is Byteonian Mafia wars. Byteberg wonders what should be the final shape of the movie climax scenes, which will be a spectacular gunfire exchange.

gangsters participate in this scene, numbered, for simplicity, using consecutive numbers from to . When the tension reaches its critical point, each gangster pulls out his weapon and takes aim at another gangster. Nobody gets aimed at by more than one gangster. Gangsters are poor, but well trained-each can shoot only once, however this shot is always accurate and always deadly.

At some point, one of the thugs cannot withstand the tension any longer and the shooting starts.

The director has determined the initial order in which gangsters have to pull the triggers. Namely, the gangster shoots towards the gangster at the precise moment , unless gangster already has been killed by that time. The gangster is killed exactly at the same moment when someone shoots in his direction.

The director would like to know how many gangsters will be alive at the end of this scene. Byteberg is not yet completely certain concerning the order in which the gangsters have to shoot. From time to time he commands to change one of the values . After every such change he would like to know the number of gangsters who would survive, referring to the new order in which gangsters shoot (taking into account all changes made so far).

Input

The third line contains integers (), describing the initial order in which the gangsters are shooting: the initial value is equal to .

The fourth line contains one integer (), denoting the number of the changes of the values of as planned by Byteberg. Next lines contain a description of these changes. The -th line contains two integers and (), describing that the -th change consists in setting the value of to . Numbers are pairwise distinct.

Output

Your program should produce exactly lines. The first line should contain the number of gangsters who survive the shooting, assuming the initial order of shooting. The -th of the following lines should present the number of survived gangsters, assuming that the order of shooting is determined by the sequence after performing all the changes-from the first to the -th.

Example

For the input data:

4
2 3 4 1
1 2 3 4
3
1 8
2 7
3 6

the correct result is:

2
2
1
1

Task author: Adam Karczmarz.