#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
struct Treap
{
    struct Node
    {
        int key;
        int pr;
        Node *l,*r;
        int lft;
        int rgt;
        int sz;
        int ans;
        Node(int x)
        {
            key=lft=rgt=x;
            pr=rand();
            ans=1;
            l=r=NULL;
        }
        void con()
        {
            sz=1;
            ans=1;
            lft=rgt=key;
            if(l)
            {
                sz+=l->sz;
                lft=l->lft;
                ans+=l->ans;
                if(key==l->rgt)ans--;
            }
            if(r)
            {
                sz+=r->sz;
                rgt=r->rgt;
                ans+=r->ans;
                if(key==r->lft)ans--;
            }

        }
        void output()
		{
			if(l)l->output();
			cout<<key<<endl;
			if(r)r->output();
		}
    };
    Node *node;
    Treap()
    {
        node=NULL;
    }
    void Merge(Node *&T,Node *L,Node *R)
    {
        if(!L)
        {
            T=R;
            return ;
        }
        if(!R)
        {
            T=L;
            return ;
        }
        if(L->pr > R->pr)
        {
            T=L;
            Merge(T->r,L->r,R);
        }
        else
        {
            T=R;
            Merge(T->l,L,R->l);
        }
        T->con();
    }
    void Split_sz(Node *T,Node *&L,Node *&R,int x)
    {
        if(!T)
        {
            L=R=NULL;
            return ;
        }
        int SZ=1;
        if(T->l)SZ+=T->l->sz;
        if(SZ<=x)
        {
            L=T;
            Split_sz(T->r,L->r,R,x-SZ);
        }
        else
        {
            R=T;
            Split_sz(T->l,L,R->l,x);
        }
        T->con();
    }
    void Delete(int x)
    {
        Node *L,*R,*MID;
        Split_sz(node,L,R,x);
        Split_sz(L,L,MID,x-1);
        Merge(node,L,R);
    }
    void Insert(int x,int col)
    {
        Node *L,*R,*MID;
        Split_sz(node,L,R,x-1);

        MID = new Node(col);

        Merge(L,L,MID);
        Merge(node,L,R);
    }
    void Change_colour(int x,int col)
    {
        Delete(x);
        Insert(x,col);
    }
    int query(int t,int a,int b)
    {
        if(t==1)
        {
            Delete(a);
            //cout<< (node->ans) <<endl;
        }
        else if(t==2)
        {
            Insert(a,b);
            //cout<< (node->ans) <<endl;
            //cout<<"line128\n";
        }
        else if(t==3)
        {
            Change_colour(a,b);
            //cout<< (node->ans) <<endl;
        }
        else if(t==4)
        {
            cout<< (node->ans) <<endl;
        }
        //node->output();
    }
};
Treap trp;
int main()
{
    int n,i,j,t,a,b,c;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a;
        //cout<<i<<endl;
        trp.query(2,i+1,a);
    }
    cin>>t;
    while(t--)
    {
        cin>>a;
        if(a==4)
        {
            trp.query(4,0,0);
        }
        if(a==1)
        {
            cin>>b;
            trp.query(1,b,0);
        }
        if(a==3)
        {
            cin>>b>>c;
            trp.query(3,b,c);
        }
        if(a==2)
        {
            cin>>b>>c;
            trp.query(2,b,c);
        }
    }
    return 0;
}