#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int M = 2e5+5;
const int B = 150;
int n,ll;
int a[M];
int t[M];
int fix[M];
int cur;
set<pair<int,int>> s;
vector <vector<pair<int,int>>> v;
vector <pair<int,int>> pos;
pair <int,int> nxt[M];
int nb = (n-1+B-1)/B;
void calc(int j) {
for (int i = v[j].size()-1; i >= 0; i--) {
auto it = s.upper_bound(v[j][i]);
if (it == s.end()) {
nxt[v[j][i].second] = {1,n+1};
continue;
}
auto res = *it;
if (fix[res.second] != fix[v[j][i].second]) {
nxt[v[j][i].second] = {1,res.first};
continue;
}
nxt[v[j][i].second] = {nxt[res.second].first+1,nxt[res.second].second};
}
}
void solve() {
v.clear();
v.resize(M);
s.clear();
for (int i = 0; i < n; i++) t[i] = INT_MAX;
pair<int,int> pos[M];
for (int i = 0; i < n; i++) {
pos[i] = {a[i],i};
}
sort(pos,pos+n);
for (int i = 0; i < n; i++) {
s.insert(pos[i]);
v[i/B].push_back(pos[i]);
t[i/B] = min(t[i/B],pos[i].first);
fix[pos[i].second] = i/B;
}
for (int i = 0; i < nb; i++) {
calc(i);
}
}
int getans() {
int cur = (*s.begin()).second;
int res = 0;
while (cur <= n) {
res += nxt[cur].first;
cur = nxt[cur].second;
}
return res;
}
int findg(int pos) {
int l = 0; int r = nb-1;
int id = 0;
while (l <= r) {
int mid = (l+r)/2;
if (t[mid] <= pos) {
id = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return id;
}
void remove(int x) {
pair<int,int> res = {a[x],x};
int j = fix[x];
s.erase(res);
auto it = find(v[j].begin(),v[j].end(),res);
v[j].erase(it);
t[j] = INT_MAX;
for (auto i:v[j]) {
t[j] = min(t[j],i.first);
}
}
void add(int x, int pos) {
a[x] = pos;
int j = findg(pos);
s.insert({a[x],x});
v[j].push_back({a[x],x});
if (v[j].size() > 2*B) {
solve();
return;
}
sort(v[j].begin(),v[j].end());
t[j] = min(t[j],a[x]);
fix[x] = j;
calc(j);
}
void init(int N, int L, int X[]) {
n = N; ll = L;
nb = (n-1+B-1)/B;
for (int i = 0; i < n; i++) {
a[i] = X[i-1];
}
solve();
}
int update(int i, int y) {
remove(i);
add(i,y);
int res = getans();
return res;
}
