#include<iostream>
#include<cstdio>
#define N 250000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
void Adder(int &x,int d)
{
    x=(x<d)?d:x;
    return;
}
int n,q,ans,tong[N+1],length,L[N+1],dp[N+1],dp2[N+1];
int main()
{
    int x,y,l,r;
    n=read();
    for (int i=1;i<=n;++i) L[i]=read();
    q=read();
    while (q--)
    {
	x=read(),y=read(),l=read()+1,r=read(),L[x]=y,length=ans=0;
	for (int i=l;i<=r;++i) tong[++length]=L[i];
        for (int i=1;i<=length;++i) dp[i]=dp2[i]=1;
	for (int i=1;i<=length;++i)
	    for (int j=1;j<=i-1;++j)
	    {
		if (tong[j]<tong[i]) Adder(dp2[i],dp[j]+1);
		if (tong[j]>tong[i]) Adder(dp[i],dp2[j]+1);
	    }
	for (int i=1;i<=length;++i) Adder(ans,dp[i]),Adder(ans,dp2[i]);
	printf("%d\n",ans);
    }
    return 0;
}