As you might already know, Ada the Ladybug is a farmer. She has a very long furrow with many kinds of vegetables (represented by integer numbers). Whenever she wants to harvest a single vegetable, she always replace it with another vegetable (possibly same kind).

After each replacement, she wants to know the number of vegetables of the same kind (at the new vegetable) which are before it (have lower position in furrow).

Input

The first line of input contains 1 ≤ N, Q ≤ 2*10⁵ , the length of furrow and number of harvests.

The next line contains N numbers 0 ≤ A_i ≤ 10⁹ the kind of vegetable which is currently on i^th spot in furrow (indexed from 0).

The next Q lines contains two numbers 0 ≤ i < N (the index of harvested plant) and 0 ≤ a ≤ 10⁹ (the kind of newly planted vegetable)

Output

For each harvest, print the number of vegetables of the same kind before the newly planted vegetable.

Example Input

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

Example Output

1
3
0
1
2

Example Input 2

10 10
2 3 5 3 9 3 5 2 9 9
7 2
0 5
0 2
1 2
9 2
4 3
8 2
4 2
2 5
3 5

Example Output 2

1
0
0
1
3
1
3
2
0
1