402866: GYM100923 J Por Costel and Pinball

Por Costel the pig is playing pinball. After many hours of studying the game by hitting the pinball table with his snout, Por Costel thinks that he figured out how it works.

There are springs on the pinball table that can launch the ball forward. If you look at the table from above, the -th spring is the -th from left to right. Springs are also characterized by their vertical position, that is, each spring also has a vertical coordinate .

If the ball hits the -th spring, the spring lauches it to another spring > . We say, in this case, that the ball bounces from the -th spring to the -th spring. There are two possibilities: Bounce up: , only if the last bounce was down. Bounce down: , only if the last bounce was up.

The first bounce doesn't have any restrictions: Por Costel launches the ball to the first spring, then the ball bounces either up or down or proceeds to bounce on a subsequence of springs that satisfy the above restrictions. Por Costel's score is the number of springs it bounces off of. Once the ball goes past the last spring, it stops.

Por Costel has spent a lot of time calculating the maximum score he can achieve if you launches the ball correctly. However, what he doesn't know is that (by hitting the table with his snout) he makes some springs change their vertical coordinate . Help Por Costel find the maximum score he can get at every moment.

The input file pinball.in contains on its first line the integer (). The second line contains integer numbers, the -th of which is the vertical coordinate of the -th spring (). The third line contains the number () and each of the next lines contain two numbers each, and () representing the fact that the -th spring changes its vertical coordinate to .

It is guaranteed that there will never be two distinct indices and such that

The output should contain lines. The first line should be the answer for the initial array and the next lines should be the answers after each of the changes.

10
1 10 2 5 6 3 4 8 9 7
3
1 11
7 17
8 12

7
6
8
6