#include <stdio.h>
#define NMAX 100010
#define TMAX (1<<17)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define INF 666666

int N, M, A, B;
int T[7][2*TMAX], p2a, noda, Sol;

void update(int x)
{
        int nod = TMAX+x, l, r;

        while (nod>1)
        {
                nod = nod>>1;
                l = nod<<1; r = (nod<<1)+1;
                T[0][nod] = MAX(T[0][l], T[0][r]);
                T[1][nod] = T[1][l]; T[2][nod] = T[2][r];
                T[5][nod] = T[5][l]; T[6][nod] = T[6][r];
                if (T[0][nod] == T[0][l])
                   T[3][nod] = T[3][l], T[4][nod] = T[4][l];
                else
                    T[3][nod] = T[3][r], T[4][nod] = T[4][r];
                if (T[5][nod]+1 == T[3][nod])
                   if (T[1][nod]+T[0][nod] > T[1][nod])
                   {
                        T[1][nod] += T[0][nod];
                        T[5][nod] = T[4][nod];
                   }
                if (T[6][nod]-1 == T[4][nod])
                   if (T[2][nod]+T[0][nod] > T[2][nod])
                   {
                        T[2][nod] += T[0][nod];
                        T[6][nod] = T[3][nod];
                   }
                if (T[0][nod] < (T[2][l]+T[1][r]))
                {
                   T[0][nod] = T[2][l]+T[1][r];
                   T[1][nod] = T[2][nod] = T[0][nod];
                }
        }
}

void query(int p1, int p2, int nod)
{
        int mij;

        if (p1>p2) return;

        if (A <= p1 && p2 <= B)
        {
                Sol = MAX(Sol, T[0][nod]);
                if ( (noda > 0) && (p2a+1 == p1) && ((T[2][noda]+T[1][nod]) > Sol) )
                   Sol = T[2][noda]+T[1][nod];
                p2a = p2; noda = nod;
                return;
        }

        if ( (p1 <= A && A <= p2) || (p1 <= B && B <= p2) )
        {
                mij = (p1+p2)>>1;
                query(p1, mij, nod<<1);
                query(mij+1, p2, (nod<<1)+1);
        }
}

int main()
{
        int i, j, k, tip, v;

        freopen("seqeuncequery.in", "r", stdin);

        scanf("%d", &N);
        for (i = 0; i < N; i++)
        {
                scanf("%d", &v);
                T[0][TMAX+i] = T[1][TMAX+i] = T[2][TMAX+i] = v;
                T[3][TMAX+i] = T[4][TMAX+i] = T[5][TMAX+i] = T[6][TMAX+i] = i;
        }
        for (i = 0; i < N; i++) update(i);
        
        scanf("%d", &M);

        freopen("seqeuncequery.out", "w", stdout);
        for (k = 0; k < M; k++)
        {
                scanf("%d %d", &i, &j);
                i--; j--;
                if (tip == 0)
                {
                        T[0][TMAX+i] = T[1][TMAX+i] = T[2][TMAX+i] = j;
                        update(i);
                }
                else
                {
                        A = i; B = j;
                        Sol = -INF;
                        noda = 0;
                        query(0, TMAX-1, 1);
                        printf("%d\n", Sol);
                }
        }

        return 0;
        
}