#include <bits/stdc++.h>
#define INF (0x3f3f3f3f)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MAXQ = 250055;
const int MAXLV = 19;
const int MX = 131072;

int seg[MX*2];

void upd(int i, int x) {
	i += MX-1;
	seg[i] = x;
	i >>= 1;
	while(i) {
		seg[i] = max(seg[i<<1], seg[i<<1|1]);
		i >>= 1;
	}
}

int getL(int i, int x) {
	i += MX-2;
	while((i & i-1) && seg[i] < x)
		i = i-1 >> 1;
	if(seg[i] < x) return 0;
	while(i < MX) {
		i <<= 1;
		i |= x <= seg[i|1];
	}
	return x == seg[i] ? i+1-MX : 0;
}

int getR(int i, int x) {
	i += MX;
	while((i & i+1) && seg[i] < x)
		i = i+1 >> 1;
	if(seg[i] < x) return 0;
	while(i < MX) {
		i <<= 1;
		i |= seg[i] < x;
	}
	return x == seg[i] ? i+1-MX : 0;
}

struct LINE {
	int s, e, y, c;
} E[MAXLV][MAXN];

struct GROUP {
	int s, e, i;
} G[MAXLV][MAXN];

int _B[MAXLV][MAXQ];
int NI[MAXLV][MAXN];

struct EVNODE { int i, y, e; } EV[MAXN]; int EVn;
LINE NE[MAXN];
int QV[MAXQ+MAXN], QVs[MAXN], QVdeg[MAXN], _QVi[MAXN];
bool isNes[MAXN];

LINE LNE[MAXN], RNE[MAXN], SLNE[MAXN];
int SLNEdeg[MAXN], SLNEi[MAXN];
int FH[MAXLV][MAXN], _FH[MAXLV][MAXN], AST[MAXN];
bool visited[MAXN], dead[MAXN];

int A[MAXN];
int B[MAXQ], C[MAXQ];

int Ans[MAXQ];
int N, Q;

int idxToGidx(const int lv, const int x, const int X) {
	if(!x) return 0;
	int s = 1, e = X, m;
	while(s < e) {
		m = s+e >> 1;
		if(x < G[lv][m].s) e = m-1;
		else if(G[lv][m].e < x) s = m+1;
		else return m;
	}
	return s;
}

void make(const int lv, const int X, int &En) {
	memcpy(G[lv+1], G[lv], (X+1) * sizeof(GROUP));
	for(int i = X; i; i--) if(FH[lv][i]) G[lv+1][i].i = 0;
	int LNEn = 0;
	memset(visited, 0, (X+1) * sizeof(bool));
	for(int i = 1, x; i <= X; i++) if(FH[lv][i]) {
		x = idxToGidx(lv, getL(G[lv][i].s, FH[lv][i]), X);
		if(!x) continue;
		if(FH[lv][x]) {
			visited[x] = true;
			RNE[x] = {x, i, FH[lv][i], 1};
		} else LNE[++LNEn] = {x, i, FH[lv][i], 1};
	}
	for(int i = X, x; i; i--) if(FH[lv][i] && !visited[i]) {
		x = idxToGidx(lv, getR(G[lv][i].s, FH[lv][i]), X);
		if(x) {
			visited[i] = true;
			RNE[i] = {i, x, FH[lv][i], 1};
		}
	}
	memset(SLNEdeg, 0, X+1 << 2);
	for(int i = LNEn; i; i--) SLNEdeg[LNE[i].s]++;
	SLNEi[1] = 1;
	for(int i = 1; i < X; i++) SLNEi[i+1] = SLNEi[i] + SLNEdeg[i];
	for(int i = LNEn; i; i--) SLNE[SLNEi[LNE[i].s]++] = LNE[i];
	memcpy(LNE+1, SLNE+1, LNEn * sizeof(LINE));
	memset(dead, 0, (En+1) * sizeof(bool));
	for(int x = 1, i = 1, n = 0; x <= X; x++) {
		while(n && E[lv][AST[n]].e == x) n--;
		while(i <= En && E[lv][i].s == x) {
			AST[++n] = i;
			i++;
		}
		while(n && E[lv][AST[n]].y <= FH[lv][x]) {
			dead[AST[n]] = true;
			n--;
		}
	}
	int NEn = 0;
{
	int ei = 1, li = 1, rx = 1;
	pii ert, lrt, rrt, mnrt;
	while(true) {
		while(ei <= En && dead[ei]) ei++;
		while(rx <= X && !visited[rx]) rx++;

		if(En < ei && LNEn < li && X < rx) break;

		ert = ei <= En ? pii( E[lv][ei].s, -E[lv][ei].y ) : pii( INF, INF );
		lrt = li <= LNEn ? pii( LNE[li].s, -LNE[li].y ) : pii( INF, INF );
		rrt = rx <= X ? pii( RNE[rx].s, -RNE[rx].y ) : pii( INF, INF );

		mnrt = min({ ert, lrt, rrt });
		if(mnrt == ert) E[lv+1][++NEn] = E[lv][ei++];
		else if(mnrt == lrt) E[lv+1][++NEn] = LNE[li++];
		else E[lv+1][++NEn] = RNE[rx++];
	}
}
	En = NEn;
}

int getEVNesIdx(const int y) {
	if(y < EV[EVn].y) return 0;
	int s = 1, e = EVn, m;
	while(s < e) {
		m = s+e >> 1;
		if(EV[m].y <= y) e = m;
		else s = m+1;
	}
	return EV[s].i;
}

void solve(const int lv, const int qsi, const int qei, int X, int En, int hidden) {
	if(qsi == qei) {
		const int x = B[qsi], y = C[qsi], idx = G[lv][x].s;
		if(getL(idx, y)) hidden++;
		if(getR(idx, y)) hidden++;
		for(int i = En; i; i--)
			if(E[lv][i].e < x || x < E[lv][i].s || y < E[lv][i].y)
				hidden += E[lv][i].c;
		Ans[qsi] = hidden;
		return;
	}
	const int _X = X;
	X = 0;
	for(int i = 1; i <= _X; i++) {
		if(X && !G[lv][X].i && !G[lv][i].i)
			G[lv][X].e = G[lv][i].e;
		else G[lv][++X] = G[lv][i];
		NI[lv][i] = X;
	}
	memcpy(_B[lv]+qsi, B+qsi, qei-qsi+1 << 2);
	for(int i = qsi; i <= qei; i++) B[i] = NI[lv][B[i]];
{
	int n = 0;
	for(int i = 1; i <= En; i++) {
		E[lv][i].s = NI[lv][ E[lv][i].s ];
		E[lv][i].e = NI[lv][ E[lv][i].e ];
		if(E[lv][i].s == E[lv][i].e)
			hidden += E[lv][i].c;
		else E[lv][++n] = E[lv][i];
	}
	En = n;
}
	memset(QVdeg, 0, X+1 << 2);
	for(int i = qsi; i <= qei; i++) QVdeg[B[i]]++;
	for(int i = 1; i < X; i++) QVs[i+1] = QVs[i] + QVdeg[i] + 1;
	memcpy(_QVi, QVs, X+1 << 2);
	for(int i = qsi; i <= qei; i++) QV[_QVi[B[i]]++] = C[i];
	for(int i = X; i; i--) QV[_QVi[i]] = 0;
	memset(isNes, 0, (En+1) * sizeof(bool));
	EVn = 0;
	for(int x = 1, i = 1; x <= X; x++) {
		while(EVn && EV[EVn].e == x) EVn--;
		while(i <= En && E[lv][i].s == x) {
			EV[++EVn] = {i, E[lv][i].y, E[lv][i].e};
			i++;
		}
		if(G[lv][x].i) isNes[ getEVNesIdx( A[ G[lv][x].s ] ) ] = true;
		int *it = QV + QVs[x];
		while(*it) {
			isNes[ getEVNesIdx(*it) ] = true;
			it++;
		}
	}
	const int _En = En;
	En = 1; NE[1] = E[lv][1];
	for(int i = 2; i <= _En; i++) {
		if(!isNes[i]
			&& NE[En].s == E[lv][i].s
			&& NE[En].e == E[lv][i].e)
			NE[En].c += E[lv][i].c;
		else NE[++En] = E[lv][i];
	}
	memcpy(E[lv], NE, (En+1) * sizeof(LINE));
	
	const int qmi = qsi + qei >> 1;
	memset(FH[lv], 0, X+1 << 2);
	for(int i = X; i; i--) if(G[lv][i].i) FH[lv][i] = A[G[lv][i].s];
	for(int i = qsi; i <= qmi; i++) FH[lv][B[i]] = 0;
	for(int i = X; i; i--) if(FH[lv][i]) upd(G[lv][i].s, FH[lv][i]);
{
	int leftEn = En;
	make(lv, X, leftEn);
	solve(lv+1, qsi, qmi, X, leftEn, hidden);
}
	for(int i = X; i; i--) if(FH[lv][i]) upd(G[lv][i].s, 0);
	memset(FH[lv], 0, X+1 << 2);
	for(int i = qsi; i <= qmi; i++) FH[lv][B[i]] = C[i];
	for(int i = X; i; i--) if(G[lv][i].i) {
		_FH[lv][i] = A[G[lv][i].s];
		if(FH[lv][i]) A[G[lv][i].s] = FH[lv][i];
	}
	for(int i = qmi+1; i <= qei; i++) FH[lv][B[i]] = 0;
	for(int i = X; i; i--) if(FH[lv][i]) upd(G[lv][i].s, FH[lv][i]);
{
	int rightEn = En;
	make(lv, X, rightEn);
	solve(lv+1, qmi+1, qei, X, rightEn, hidden);
}
	for(int i = X; i; i--) if(G[lv][i].i) {
		A[G[lv][i].s] = _FH[lv][i];
		if(FH[lv][i]) upd(G[lv][i].s, 0);
	}
	memcpy(B+qsi, _B[lv]+qsi, qei-qsi+1 << 2);
}

namespace INIT {
	bitset<MAXN> chk;
	int I[MAXN];
	pii V[MAXN];
	int Vn;

	void run(int &En) {
		for(int i = Q; i; i--) chk[B[i]] = true;
		Vn = En = 0;
		for(int i = 1; i <= N; i++) if(!chk[i]) {
			while(Vn && V[Vn].se < A[i]) Vn--;
			if(Vn && V[Vn].se == A[i]) {
				I[V[Vn].fi] = i;
				V[Vn].fi = i;
			} else V[++Vn] = {i, A[i]};
		}
		for(int i = 1; i <= N; i++) if(I[i])
			E[0][++En] = {i, I[i], A[i], 1 == i || i == N ? 0 : 1};
		for(int i = N; i; i--)
			G[0][i] = {i, i, chk[i] ? 1 : 0};
		for(int i = N; i; i--) if(!chk[i]) upd(i, A[i]);
		Vn = 0;
		for(int i = 2; i < N; i++) {
			while(Vn && V[Vn].se < A[i]) Vn--;
			if(Vn && V[Vn].se == A[i]) Ans[0]++;
			else V[++Vn] = {i, A[i]};
		}
	}
}

void solve() {
	for(int i = N; i; i--) A[i+1] = A[i];
	A[1] = A[N+2] = INF;
	N += 2;
	for(int i = Q; i; i--) B[i]++;

	int En = 0;
	INIT::run(En);
	solve(0, 1, Q, N, En, 0);
}

vector<long long int> count_cable(vector<int> _A, vector<pair<int, int>> _C) {
    N = _A.size();
    Q = _C.size();
    for(int i = 1; i <= N; i++) A[i] = _A[i-1];
    for(int i = 1; i <= Q; i++) tie(B[i], C[i]) = _C[i-1];
    
    solve();
    
    vector<long long int> result(Q+1, 0ll);
    for(int i = 0; i <= Q; i++) result[i] = Ans[i];
    return result;
}