L. Quicksort
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of positive integers, define one quicksort operation as the following:

  • Choose any integer in the array as the pivot.
  • Move all items strictly less than the pivot to its left, maintaining their original order.
  • Move all items strictly greater than the pivot to its right, maintaining their original order.
  • Any items equal to the pivot will be grouped together with it.

For example, if we have the array $$$\{5, 4, 6, 5, 3, 1, 4, 2\}$$$ and we choose the pivot to be $$$4$$$, the new array becomes $$$\{3, 1, 2, 4, 4, 5, 6, 5\}$$$.

Given an array of $$$n$$$ integers and $$$q$$$ modification queries in the form $$$a_i = v$$$, find the minimum number of quicksort operations required to sort the array into ascending order after each operation. The updates are permanent.

Input

The first line contains $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains $$$q$$$ ($$$1 \le q \le 10^5$$$).

Each of the next $$$q$$$ lines contains $$$i$$$ and $$$v$$$ ($$$1 \le i \le n$$$, $$$1 \le v \le 10^9$$$), indicating a modification query in the form $$$a_i = v$$$.

Output

After each modification query, print the minimum number of quicksort operations required to sort the array.

Example
Input
8
8 5 4 6 1 7 3 5
8
7 8
7 4
6 6
4 1
4 7
2 8
5 4
5 7
Output
3 3 2 2 3 3 2 2