ADACROP - Ada and Harvest


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 anoher 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 possition in furrow).

Input

The first line of input containts 1 ≤ N, Q ≤ 2*105 , the length of furrow and number of harvests.

The next line contains N numbers 0 ≤ Ai ≤ 109 the kind of vegetable which is currently on ith spot in furrow (indexed from 0).

The next Q lines contains two numbers 0 ≤ i < N (the index of harvested plant) and 0 ≤ a ≤ 109 (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

hide comments
mhasan01: 2020-07-06 21:32:50

Accepted using Treap :)
You need to compress it and use array of Treaps, each treap for each value

daviddamian01: 2020-05-23 17:46:26

Tried a treap with buckets (both map and unordered_map) and then segment tree with buckets (the same). Both data structures got TLE.

urielguz33: 2020-01-31 08:02:03

Changing unordered_map to map as xteq said changed my veredict from TLE to ACC for some reason, I thought unordered maps were supposed to be faster...

xteq: 2019-07-16 01:16:08

Do not use std::unordered_map with standard hashing function! It costed me many TLEs.

DK...: 2019-03-18 14:10:08

nlog(n) works fine!

anirudnits: 2018-08-28 13:33:16

using BIT but still getting TLE, any suggestions?


Added by:Morass
Date:2017-09-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All