题意首先可以转化为求笛卡尔树上大小为 $4$ 的连通块个数（对应六元环的六个点为这四个点和最上面节点代表区间的右端点 $+1$，左端点 $-1$），但不能包含根节点（六元环不包含 $0$，$n+1$），用一个简单的 $\text{dp}$ 求解就行了。

修改操作体现在笛卡尔树上其实就是上旋，容易发现，对于一条方向相同的链，一个点上旋到链顶只会产生 $O(1)$ 的父子关系改变，也只会产生 $O(1)$ 的 $\text{dp}$ 数组的改变。

所以直接用 $\text{LCT}$ 去维护就行了。

#include<cstdio>
#define int unsigned
namespace IO{
	#define BUFSIZE 10000000
	struct read{
		char buf[BUFSIZE],*p1,*p2,c;
		read():p1(buf),p2(buf){}
		inline char gc(void){
			return p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++;
		}
		inline read& operator >>(int& x){
			for(c=gc(),x=0;c<'0'||c>'9';c=gc());
			for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
			return *this;
		}
	}in;
	struct write{
		char buf[BUFSIZE],*p1,*p2,s[50];
		int tp;
		write():p1(buf),p2(buf+BUFSIZE){}
		~write(){flush();}
		inline void flush(void){
			fwrite(buf,1,p1-buf,stdout);
			p1=buf;
		}
		inline void pc(char const &c){
			if(p1==p2)flush();
			*p1++=c;
		}
		inline write& operator <<(int x){
			do{s[tp++]=x%10+'0',x/=10;}while(x);
			while(tp)pc(s[--tp]);
			return *this;
		}
		inline write& operator <<(char const &x){
			pc(x);
			return *this;
		}
	}out;
}
using IO::in;
using IO::out;
int n,q,rt,ans,d[500010],ch[500010][2],fa[500010],dp[500010][5];
unsigned long long v[500010];
inline void update(int p){
	if(!p) return;
	int x=ch[p][0],y=ch[p][1];
	int cg=0,res=0;
	ans-=dp[p][4];
	res=dp[y][1]+dp[x][1];
	if(res!=dp[p][2])cg=1,dp[p][2]=res;
	res=dp[y][2]+dp[x][1]*dp[y][1]+dp[x][2];
	if(res!=dp[p][3])cg=1,dp[p][3]=res;
	res=dp[y][3]+dp[x][1]*dp[y][2]+dp[x][2]*dp[y][1]+dp[x][3];
	if(res!=dp[p][4])cg=1,dp[p][4]=res;
	ans+=dp[p][4];
	if(cg) update(fa[p]);
}
void dfs(int p){
	int x=ch[p][0],y=ch[p][1];
	if(x)dfs(x);if(y)dfs(y);
	for(int i=1;i<=4;i++){
		dp[p][i]=0;
		for(int j=0;j<=i-1;j++)dp[p][i]+=dp[x][j]*dp[y][i-j-1];
	}
	ans+=dp[p][4];
}
namespace LCT{
	int s[500010][2],f[500010],tp[500010];
	inline int isroot(int x){return s[f[x]][1]!=x&&s[f[x]][0]!=x;}
	inline void rotate(int x){
		int const y=f[x],z=f[y],k=(s[y][1]==x);if(!isroot(y))s[z][y==s[z][1]]=x;
		f[x]=z,f[y]=x,s[x][k^1]&&(f[s[x][k^1]]=y),s[y][k]=s[x][k^1],s[x][k^1]=y;
		tp[x]=tp[y];
	}
	inline void splay(int x){
		while(!isroot(x)){
			if(!isroot(f[x]))rotate((s[f[x]][0]==x)^(s[f[f[x]]][0]==f[x])?x:f[x]);
			rotate(x);
		}
	}
	inline void acc(int x){
		splay(x);
		tp[s[x][1]]=tp[x];
		s[x][1]=0;
	}
	inline void link(int p,int x){
		if(x==0) return;
		splay(x);
		int type=x>p;
		ch[p][type]=x,d[x]=type;
		fa[x]=p,update(p),acc(p);
		if(!s[p][0]&&!s[p][1])tp[p]=type;
		if(tp[p]==type&&((!s[x][0]&&!s[x][1])||tp[x]==type))s[p][1]=x;
		f[x]=p;
	}
	inline void cut(int p,int x){
		if(!x) return;
		splay(x);
		int type=x>p;
		ch[p][type]=0,fa[x]=0;
		update(p),acc(p);
		f[x]=0;
	}
	inline bool cmp(int x,int y){return v[x]>v[y]||(v[x]==v[y]&&x<y);}
	inline int findnxt(int x){
		int nw=s[x][0],res=0;
		while(1)
			if(cmp(x,nw)){
				res=nw;
				if(!s[nw][0])return splay(nw),res;
				nw=s[nw][0];
			}else{
				if(!s[nw][1])return splay(nw),res;
				nw=s[nw][1];
			}
	}
	inline void upd(int x,int val){
		int l=ch[x][0],r=ch[x][1];
		cut(x,l),cut(x,r);
		v[x]+=val;
		while(fa[x]&&cmp(x,fa[x])){
			splay(x);
			if(s[x][0]){
				int fat=findnxt(x),h=fa[x];
				cut(h,x);
				if(d[x])link(h,l),l=fat;
				else link(h,r),r=fat;
				if(fa[fat]){
					int g=fa[fat];
					cut(g,fat),link(g,x);
				}
			}else{
				int fat=fa[x];
				cut(fat,x);
				if(d[x])link(fat,l),l=fat;
				else link(fat,r),r=fat;
				if(fa[fat]){
					int g=fa[fat];
					cut(g,fat),link(g,x);
				}
			}
		}
		link(x,l),link(x,r);
		if(!fa[x]) rt=x;
	}
}
int st[500010],*tp=st;
signed main(){
// 	freopen("45.in","r",stdin);
// 	freopen("45.out","w",stdout); 
	in>>n;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)dp[i][1]=dp[i][0]=1;
	for(int i=1,x;i<=n;i++)in>>x,v[i]=x;
	v[0]=-1;
	for(int i=1;i<=n;i++){
		while(v[*tp]<v[i])ch[i][0]=*tp--;
		if(tp!=st)ch[*tp][1]=i;
		*++tp=i;
	}
	for(int i=1;i<=n;i++)fa[ch[i][0]]=fa[ch[i][1]]=i,d[ch[i][1]]=1;v[0]=d[0]=fa[0]=0;
	for(int i=1;i<=n;i++)LCT::f[i]=fa[i];
	for(int i=1;i<=n;i++)if(!fa[i]){rt=i;break;}
	dfs(rt);
	in>>q;
	while(q--){
		int x,y;
		in>>x>>y;
		LCT::upd(x,y);
		out<<(ans-dp[rt][4])<<'\n';
	}
	return 0;
}