#include<bits/stdc++.h>
#include "bubblesort2.h"
#define mp make_pair
using namespace std;
using ll=long long;
const int N=1e6+13;
struct Segtree{
int st[N << 2];
int lazy[N << 2];
void fix(int id, int l, int r){
st[id] += lazy[id];
if(l!=r){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id]=0;
}
void update(int id, int l, int r, int u, int v, int val){
fix(id, l, r);
if(l > v || r < u) return;
if(u<=l && r<=v){
lazy[id] += val;
fix(id, l, r);
return;
}
int mid=l+r >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid+1, r, u, v, val);
st[id]=max(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u){
fix(id, l, r);
if(l > u || r < u) return -1e9;
if(l==r) return st[id];
int mid=l+r >> 1;
int get1=get(id << 1, l, mid, u);
int get2=get(id << 1 | 1, mid+1, r, u);
return max(get1, get2);
}
} st;
int n, q;
int a[N];
vector<pair<int, int>> vt;
int x[N], v[N];
int res[N];
void scan(){
cin >> n >> q;
for(int i=0; i<n; i++){
cin >> a[i];
vt.emplace_back(a[i], i);
}
for(int i=0; i<q; i++){
cin >> x[i] >> v[i];
vt.emplace_back(v[i], x[i]);
}
sort(begin(vt), end(vt));
for(int i=0; i<n; i++){
a[i]=upper_bound(begin(vt), end(vt), mp(a[i], i))-begin(vt);
}
for(int i=0; i<q; i++){
v[i]=upper_bound(begin(vt), end(vt), mp(v[i], x[i]))-begin(vt);
}
}
void upd(int id, int val){
st.update(1, 1, n+q, a[id], a[id], id*val);
st.update(1, 1, n+q, a[id]+1, n+q, -val);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> VQ) {
n = (int)A.size();
q = (int)X.size();
vt.clear(); vt.reserve(n + q);
for (int i = 0; i < n; ++i) {
a[i] = A[i];
vt.emplace_back(a[i], i);
}
for (int i = 0; i < q; ++i) {
x[i] = X[i];
v[i] = VQ[i];
vt.emplace_back(v[i], x[i]);
}
sort(begin(vt), end(vt));
for (int i = 0; i < n; ++i) {
a[i] = int(upper_bound(begin(vt), end(vt), mp(A[i], i)) - begin(vt));
}
for (int i = 0; i < q; ++i) {
v[i] = int(upper_bound(begin(vt), end(vt), mp(VQ[i], x[i])) - begin(vt));
}
memset(st.st, 0, sizeof(st.st));
memset(st.lazy, 0, sizeof(st.lazy));
auto do_upd = [&](int id, int val) {
st.update(1, 1, n + q, a[id], a[id], id * val);
st.update(1, 1, n + q, a[id] + 1, n + q, -val);
};
for (int i = 0; i < n; ++i) do_upd(i, 1);
vector<int> S(q);
for (int i = 0; i < q; ++i) {
do_upd(x[i], -1);
a[x[i]] = v[i];
do_upd(x[i], 1);
S[i] = st.st[1];
}
return S;
}
