#ifndef rtgsp
#include "bubblesort2.h"
#endif // rtgsp
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, inf = 1e9;
int n, m, q, a[maxn], x[maxn], v[maxn];
vector<int> cmp, vals[maxn];
set<int> pos[maxn];
struct ST
{
ll st[4*maxn], lazy[4*maxn];
void build (int node, int l, int r)
{
if (l == r)
{
st[node] = - *pos[l].begin();
return;
}
int m = (l + r)/2;
build(2*node, l, m);
build(2*node + 1, m + 1, r);
st[node] = max(st[2*node], st[2*node + 1]);
}
void down (int node)
{
st[2*node] = st[2*node] + lazy[node];
lazy[2*node] = lazy[2*node] + lazy[node];
st[2*node + 1] = st[2*node + 1] + lazy[node];
lazy[2*node + 1] = lazy[2*node + 1] + lazy[node];
lazy[node] = 0;
}
void upd1 (int node, int l, int r, int idx, int val)
{
if (l == r)
{
st[node] = st[node] + val;
return;
}
down(node);
int m = (l + r)/2;
if (idx <= m) upd1(2*node, l, m, idx, val);
else upd1(2*node + 1, m + 1, r, idx, val);
st[node] = max(st[2*node], st[2*node + 1]);
}
void upd2 (int node, int l, int r, int cl, int cr, int val)
{
if (cr < l || r < cl) return;
if (cl <= l && r <= cr)
{
st[node] = st[node] + val;
lazy[node] = lazy[node] + val;
return;
}
down(node);
int m = (l + r)/2;
upd2(2*node, l, m, cl, cr, val);
upd2(2*node + 1, m + 1, r, cl, cr, val);
st[node] = max(st[2*node], st[2*node + 1]);
}
int get (int node, int l, int r, int idx)
{
if (l == r) return st[node];
down(node);
int m = (l + r)/2;
if (idx <= m) return get(2*node, l, m, idx);
else return get(2*node + 1, m + 1, r, idx);
}
}st;
vector<int> countScans (vector<int> A, vector<int> X, vector<int> V)
{
n = A.size();
for (int i = 1; i <= n; i++) a[i] = A[i - 1];
q = X.size();
for (int i = 1; i <= q; i++)
{
x[i] = X[i - 1] + 1;
v[i] = V[i - 1];
}
vector<int> S;
S.clear();
for (int i = 1; i <= n; i++) cmp.push_back(a[i]);
for (int i = 1; i <= q; i++) cmp.push_back(v[i]);
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
for (int i = 1; i <= (int)cmp.size(); i++) pos[i].insert(inf);
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
pos[a[i]].insert(-i);
}
for (int i = 1; i <= q; i++)
v[i] = lower_bound(cmp.begin(), cmp.end(), v[i]) - cmp.begin() + 1;
m = cmp.size();
st.build(1, 1, m);
for (int i = 1; i <= n; i++)
st.upd2(1, 1, m, a[i], m, -1);
for (int i = 1; i <= q; i++)
{
int prv = *pos[a[x[i]]].begin();
pos[a[x[i]]].erase(-x[i]);
int nxt = *pos[a[x[i]]].begin();
if (nxt != prv) st.upd1(1, 1, m, a[x[i]], prv - nxt);
st.upd2(1, 1, m, a[x[i]], m, 1);
a[x[i]] = v[i];
prv = *pos[a[x[i]]].begin();
pos[a[x[i]]].insert(-x[i]);
nxt = *pos[a[x[i]]].begin();
if (nxt != prv) st.upd1(1, 1, m, a[x[i]], prv - nxt);
st.upd2(1, 1, m, a[x[i]], m, -1);
S.push_back(st.st[1]);
}
return S;
}
#ifdef rtgsp
int main()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
vector<int> A, X, V;
A.clear(); X.clear(); V.clear();
cin >> N >> Q;
for (int i = 1; i <= N; i++)
{
int x;
cin >> x;
A.push_back(x);
}
for (int i = 1; i <= Q; i++)
{
int x;
cin >> x;
X.push_back(x);
}
for (int i = 1; i <= Q; i++)
{
int x;
cin >> x;
V.push_back(x);
}
auto S = countScans(A, X, V);
for (int i : S) cout << i << '\n';
}
#endif // rtgsp
