ДО 3

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvs(vector <string>  v){
    for (auto a: v){
        cout<<a<<"\n";
    }
}

void cvp(vector <pii> a){
    for (auto p: a){
        cout<<p.first<<' '<<p.second<<"\n";
    }
    cout<<"\n";
}

bool sh = 0;

int n,N;

struct nd{
    int mxl;
    int Li, Ll;
    int Ri, Rl;
};

void see(nd k){
    cout<<k.mxl<<" "<<k.Li<<" "<<k.Ll<<" "<<k.Ri<<" "<<k.Rl<<"\n";
}

int L, R;
nd no;//значит нет узла

struct tree{
    vector <nd> v;

    void show(){
        cout<<"v\n";
        for (int i = 0; i < 2 * N - 1; ++i){
            cout<<"id = "<<i<<"\n";
            see(v[i]);
        }
    }

    void mk(int i){//сделать узел на основе двух сыновей - make
        int un = -1;
        v[i].Li = min(v[i*2 + 1].Li, v[i*2 + 2].Li);
        v[i].Ll = v[2 * i + 1].Ll;
        if (v[i].Ll == 0){
            v[i].Ll = v[2 * i + 2].Ll;
        }
        v[i].Ri = max(v[i*2 + 1].Ri, v[i*2 + 2].Ri);
        v[i].Rl = v[2 * i + 2].Rl;
        if (v[i].Rl == 0){
            v[i].Rl = v[2 * i + 1].Rl;
        }
        v[i].mxl = max(v[i * 2 + 1].mxl, v[i * 2 + 2].mxl);

        if (v[i * 2 + 1].Ri + 1 == v[i * 2 + 2].Li){
            un = v[i * 2 + 1].Rl + v[i * 2 + 2].Ll;
            //v[i].mxl = max(un, v[i].mxl);
            if (un > v[i].mxl){

                v[i].mxl = un;
                /*if (sh){
                    cout<<"un\n";
                    cout<<"id = "<<i<<"\n";
                    see(v[i * 2 + 1]);
                    see(v[i * 2 + 2]);
                }*/
            }

            //учесть - если объединили с краев
            if ( v[2*i + 1].Li + v[2 * i + 1].Ll - 1 == v[2 * i + 1].Ri){//слева только одна п-ть 0й
                 v[i].Ll =  v[2 * i + 1].Rl + v[2 * i + 2].Ll;
            }
            if ( v[2*i + 2].Li + v[2 * i + 2].Ll - 1 == v[2 * i + 2].Ri){//слева только одна п-ть 0й
                 v[i].Rl =  v[2 * i + 1].Rl + v[2 * i + 2].Ll;
            }

        }
    }

    void bld(){
        cin>>n;
        N = log2(n);
        if (pow(2, N) < n){
            N++;
        }
        N = pow(2, N);

        no = {0, N + 10, 0, -10, 0};

        v.assign(2*N - 1, no);
        for (int i = N - 1; i < N - 1 + n; ++i){
            int x; cin>>x;
            int id = i - (N - 1);
            if (x == 0){
                nd k = {1, id, 1, id, 1};
                v[i] = k;
            }
        }

        if (sh){
            cout<<"go\n";
        }

        for (int i = N - 2; i >= 0; --i){
            mk(i);
        }

        if (sh){
            cout<<"BDL\n";
            show();
        }
    }


    void upd(int id, int x){
        id--;
        id += N - 1;
        if (x == 0){
            v[id] = {1, id - (N - 1), 1 , id - (N - 1), 1};
        }
        else if (x != 0 ){
            v[id] = no;
        }
        while (id > 0){
            id--;
            id /= 2;
            mk(id);
        }

        if (sh){
            show();
        }

    }

    nd get(int id, int l, int r){
        if (l >= L && r <=  R){
            return v[id];
        }
        else if (max(l, L) <= min(r, R)){
            nd res;
            int m = (l + r) / 2;
            nd Lft,Rgt;
            Lft = get(2 * id + 1, l, m);
            Rgt = get(2 * id + 2, m + 1, r);

            //для всех
            int un = -1;
            res.Li = min(Lft.Li, Rgt.Li);
            res.Ll = Lft.Ll;
            if (res.Ll == 0){
                res.Ll = Rgt.Ll;
            }
            res.Ri = max(Lft.Ri, Rgt.Ri);
            res.Rl = Rgt.Rl;
            if (res.Rl == 0){
                res.Rl = Lft.Rl;
            }
            res.mxl = max(Lft.mxl, Rgt.mxl);

            //если можно объединить
            if (Lft.Ri + 1 == Rgt.Li){
                un = Lft.Rl + Rgt.Ll;
                //v[i].mxl = max(un, v[i].mxl);
                if (un > res.mxl){

                    res.mxl = un;
                    /*if (sh){
                        cout<<"un\n";
                        cout<<"id = "<<i<<"\n";
                        see(v[i * 2 + 1]);
                        see(v[i * 2 + 2]);
                    }*/
                }

                //учесть - если объединили с краев
                if ( Lft.Li + Lft.Ll - 1 == Lft.Ri){//слева только одна п-ть 0й
                     res.Ll =  Lft.Rl + Rgt.Ll;
                }
                if ( Rgt.Li + Rgt.Ll - 1 == Rgt.Ri){//слева только одна п-ть 0й
                     res.Rl =  Lft.Rl + Rgt.Ll;
                }

            }

            return res;

        }
        else{
            return no;
        }
    }


};

/*
ОСТАЛОСЬ:
debug на сэмпле - ошибки
*/

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    tree T;
    T.bld();
    //if (!sh)
    cin>>m;
    for (int i = 0; i < m; ++i){
        //запрос
        string q; cin>>q;
        if (q[0] == 'Q'){
            if (sh) cout<<"ASK\n";
            cin>>L>>R; L--; R--;
            nd ans = T.get(0, 0, N - 1);
            cout<<ans.mxl<<"\n";
        }
        else{
            if (sh) cout<<"UPD\n";
            int id, x; cin>>id>>x; T.upd(id, x);

        }
    }
}

/*
Примеры
Входные данные
5
328 0 0 0 0
5
QUERY 1 3
UPDATE 2 832
QUERY 3 3
QUERY 2 3
UPDATE 2 0
Выходные данные
2
1
1
*/