#include <cstdio>
#include <cstdlib>
#include <map>
#include <vector>
using namespace std;
typedef struct Node *pnode;
struct Node {
int key, prior, cnt; // cnt nodes in subtree with the curr root (incl. root)
pnode l, r;
Node(int key) : key(key), prior(rand()), cnt(1), l(nullptr), r(nullptr) {}
};
struct Treap {
private:
pnode root;
int cnt(pnode t) {
return t ? t->cnt : 0;
}
void updCnt(pnode t) {
if (t) {
t->cnt = 1 + cnt(t->l) + cnt(t->r);
}
}
void split(pnode t, int key, pnode &l, pnode &r) {
if (!t) {
l = r = nullptr;
} else if (t->key <= key) {
split(t->r, key, t->r, r), l = t;
} else {
split(t->l, key, l, t->l), r = t;
}
updCnt(t);
}
void insert(pnode &t, pnode it) {
if (!t) {
t = it;
} else if (it->prior <= t->prior) {
insert(t->key < it->key ? t->r : t->l, it);
} else {
split(t, it->key, it->l, it->r), t = it;
}
updCnt(t);
/*
pnode l, r, res;
split(t, it->key, l, r);
merge(res, l, it);
merge(res, res, r);
*/
}
void merge(pnode &t, pnode l, pnode r) {
if (!l || !r) {
t = l ? l : r;
} else if (l->prior <= r->prior) {
merge(r->l, l, r->l), t = r;
} else {
merge(l->r, l->r, r), t = l;
}
updCnt(t);
}
void erase(pnode &t, int key) {
if (!t) {
return;
}
if (t->key == key) {
pnode temp = t;
merge(t, t->l, t->r);
delete temp;
} else {
erase(key <= t->key ? t->l : t->r, key);
}
}
int query(pnode t, int key) { // key == position
pnode l(nullptr), r(nullptr);
split(t, key - 1, l, r);
int res = (l ? l->cnt : 0);
merge(t, l, r);
return res;
}
public:
Treap() : root(nullptr) {};
void insert(int key) {
insert(this->root, new Node(key));
}
void erase(int key) {
erase(this->root, key);
}
int query(int key) {
return query(this->root, key);
}
};
int main() {
int N, Q;
scanf("%d %d", &N, &Q);
vector<int> a(N);
map<int, Treap> vegTypeTreap;
for (int i = 0; i < N; ++i) {
scanf("%d", &a[i]);
vegTypeTreap[a[i]].insert(i);
}
int pos, vegType;
while (Q--) {
scanf("%d %d", &pos, &vegType);
Treap *t = &vegTypeTreap[vegType];
printf("%d\n", t->query(pos));
if (a[pos] != vegType) {
vegTypeTreap[a[pos]].erase(pos);
vegTypeTreap[vegType].insert(pos);
a[pos] = vegType;
}
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBzdHJ1Y3QgTm9kZSAqcG5vZGU7CgpzdHJ1Y3QgTm9kZSB7CiAgICBpbnQga2V5LCBwcmlvciwgY250OyAvLyBjbnQgbm9kZXMgaW4gc3VidHJlZSB3aXRoIHRoZSBjdXJyIHJvb3QgKGluY2wuIHJvb3QpCiAgICBwbm9kZSBsLCByOwoKICAgIE5vZGUoaW50IGtleSkgOiBrZXkoa2V5KSwgcHJpb3IocmFuZCgpKSwgY250KDEpLCBsKG51bGxwdHIpLCByKG51bGxwdHIpIHt9Cn07CgpzdHJ1Y3QgVHJlYXAgewpwcml2YXRlOgogICAgcG5vZGUgcm9vdDsKCiAgICBpbnQgY250KHBub2RlIHQpIHsKICAgICAgICByZXR1cm4gdCA/IHQtPmNudCA6IDA7CiAgICB9CgogICAgdm9pZCB1cGRDbnQocG5vZGUgdCkgewogICAgICAgIGlmICh0KSB7CiAgICAgICAgICAgIHQtPmNudCA9IDEgKyBjbnQodC0+bCkgKyBjbnQodC0+cik7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgc3BsaXQocG5vZGUgdCwgaW50IGtleSwgcG5vZGUgJmwsIHBub2RlICZyKSB7CiAgICAgICAgaWYgKCF0KSB7CiAgICAgICAgICAgIGwgPSByID0gbnVsbHB0cjsKICAgICAgICB9IGVsc2UgaWYgKHQtPmtleSA8PSBrZXkpIHsKICAgICAgICAgICAgc3BsaXQodC0+ciwga2V5LCB0LT5yLCByKSwgbCA9IHQ7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgc3BsaXQodC0+bCwga2V5LCBsLCB0LT5sKSwgciA9IHQ7CiAgICAgICAgfQogICAgICAgIHVwZENudCh0KTsKICAgIH0KCiAgICB2b2lkIGluc2VydChwbm9kZSAmdCwgcG5vZGUgaXQpIHsKICAgICAgICBpZiAoIXQpIHsKICAgICAgICAgICAgdCA9IGl0OwogICAgICAgIH0gZWxzZSBpZiAoaXQtPnByaW9yIDw9IHQtPnByaW9yKSB7CiAgICAgICAgICAgIGluc2VydCh0LT5rZXkgPCBpdC0+a2V5ID8gdC0+ciA6IHQtPmwsIGl0KTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBzcGxpdCh0LCBpdC0+a2V5LCBpdC0+bCwgaXQtPnIpLCB0ID0gaXQ7CiAgICAgICAgfQogICAgICAgIHVwZENudCh0KTsKICAgICAgICAvKgogICAgICAgIHBub2RlIGwsIHIsIHJlczsKICAgICAgICBzcGxpdCh0LCBpdC0+a2V5LCBsLCByKTsKICAgICAgICBtZXJnZShyZXMsIGwsIGl0KTsKICAgICAgICBtZXJnZShyZXMsIHJlcywgcik7CiAgICAgICAgKi8KICAgIH0KCiAgICB2b2lkIG1lcmdlKHBub2RlICZ0LCBwbm9kZSBsLCBwbm9kZSByKSB7CiAgICAgICAgaWYgKCFsIHx8ICFyKSB7CiAgICAgICAgICAgIHQgPSBsID8gbCA6IHI7CiAgICAgICAgfSBlbHNlIGlmIChsLT5wcmlvciA8PSByLT5wcmlvcikgewogICAgICAgICAgICBtZXJnZShyLT5sLCBsLCByLT5sKSwgdCA9IHI7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgbWVyZ2UobC0+ciwgbC0+ciwgciksIHQgPSBsOwogICAgICAgIH0KICAgICAgICB1cGRDbnQodCk7CiAgICB9CgogICAgdm9pZCBlcmFzZShwbm9kZSAmdCwgaW50IGtleSkgewogICAgICAgIGlmICghdCkgewogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGlmICh0LT5rZXkgPT0ga2V5KSB7CiAgICAgICAgICAgIHBub2RlIHRlbXAgPSB0OwogICAgICAgICAgICBtZXJnZSh0LCB0LT5sLCB0LT5yKTsKICAgICAgICAgICAgZGVsZXRlIHRlbXA7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgZXJhc2Uoa2V5IDw9IHQtPmtleSA/IHQtPmwgOiB0LT5yLCBrZXkpOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgcXVlcnkocG5vZGUgdCwgaW50IGtleSkgeyAgIC8vIGtleSA9PSBwb3NpdGlvbgogICAgICAgIHBub2RlIGwobnVsbHB0ciksIHIobnVsbHB0cik7CiAgICAgICAgc3BsaXQodCwga2V5IC0gMSwgbCwgcik7CiAgICAgICAgaW50IHJlcyA9IChsID8gbC0+Y250IDogMCk7CiAgICAgICAgbWVyZ2UodCwgbCwgcik7CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KCnB1YmxpYzoKICAgIFRyZWFwKCkgOiByb290KG51bGxwdHIpIHt9OwoKICAgIHZvaWQgaW5zZXJ0KGludCBrZXkpIHsKICAgICAgICBpbnNlcnQodGhpcy0+cm9vdCwgbmV3IE5vZGUoa2V5KSk7CiAgICB9CgogICAgdm9pZCBlcmFzZShpbnQga2V5KSB7CiAgICAgICAgZXJhc2UodGhpcy0+cm9vdCwga2V5KTsKICAgIH0KCiAgICBpbnQgcXVlcnkoaW50IGtleSkgewogICAgICAgIHJldHVybiBxdWVyeSh0aGlzLT5yb290LCBrZXkpOwogICAgfQp9OwoKaW50IG1haW4oKSB7CiAgICBpbnQgTiwgUTsKICAgIHNjYW5mKCIlZCAlZCIsICZOLCAmUSk7CiAgICB2ZWN0b3I8aW50PiBhKE4pOwogICAgbWFwPGludCwgVHJlYXA+IHZlZ1R5cGVUcmVhcDsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkgewogICAgICAgIHNjYW5mKCIlZCIsICZhW2ldKTsKICAgICAgICB2ZWdUeXBlVHJlYXBbYVtpXV0uaW5zZXJ0KGkpOwogICAgfQoKICAgIGludCBwb3MsIHZlZ1R5cGU7CiAgICB3aGlsZSAoUS0tKSB7CiAgICAgICAgc2NhbmYoIiVkICVkIiwgJnBvcywgJnZlZ1R5cGUpOwogICAgICAgIFRyZWFwICp0ID0gJnZlZ1R5cGVUcmVhcFt2ZWdUeXBlXTsKICAgICAgICBwcmludGYoIiVkXG4iLCB0LT5xdWVyeShwb3MpKTsKICAgICAgICBpZiAoYVtwb3NdICE9IHZlZ1R5cGUpIHsKICAgICAgICAgICAgdmVnVHlwZVRyZWFwW2FbcG9zXV0uZXJhc2UocG9zKTsKICAgICAgICAgICAgdmVnVHlwZVRyZWFwW3ZlZ1R5cGVdLmluc2VydChwb3MpOwogICAgICAgICAgICBhW3Bvc10gPSB2ZWdUeXBlOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gMDsKfQ==