// submit da bi se videlo da je nesto uradjeno


#include <stdio.h>

struct bstCvor
{
    int vred;
    int bPotL, bPotD;
    int levimax, desnimin, levimin, desnimax;
    bstCvor *levi;
    bstCvor *desni;
};

struct segCvor
{
    int levagr, desnagr;
    segCvor *levo, *desno;
    bstCvor BST;
};

void FormirajBST (bstCvor cvoric, int leva, int desna, int a [])
{
    if (leva < desna)
    {
        cvoric.vred = a [(leva + desna) / 2];
        bstCvor levo, desno;
        FormirajBST (levo, leva, (leva + desna) / 2 - 1, a);
        FormirajBST (desno, (leva + desna) / 2 + 1, desna, a);
        cvoric.levi = &levo;
        cvoric.desni = &desno;
        cvoric.levimin = levo.levimin;
        cvoric.desnimax = desno.desnimax;
        cvoric.levimax = levo.desnimax;
        cvoric.desnimin = desno.levimin;
        if (levo.levimin == -1) cvoric.levimin = levo.vred;
        if (levo.desnimax == -1) cvoric.levimin = levo.vred;
        if (desno.levimin == -1) cvoric.desnimin = desno.vred;
        if (desno.desnimax == -1) cvoric.desnimax = desno.vred;
        cvoric.bPotD = desno.bPotL + desno.bPotD + 1;
        cvoric.bPotL = levo.bPotL + levo.bPotD + 1;
    }
    else
    {
        if (leva == desna)
        {
            cvoric.vred = a [leva];
            cvoric.levimin = -1;
            cvoric.desnimax = -1;
            cvoric.levimax = -1;
            cvoric.desnimin = -1;
            cvoric.bPotL = 0;
            cvoric.bPotD = 0;
        }
        else
        {
            cvoric.vred = -1;
        }
    }
}

void FormirajSegmentno (segCvor cvorak, int leva, int desna, int a [])
{
    cvorak.levagr = leva;
    cvorak.desnagr = desna;
    if (leva < desna)
    {
        bstCvor koren;
        segCvor levo, desno;
        FormirajSegmentno (levo, leva, (leva + desna) / 2, a);
        FormirajSegmentno (desno, 1 + (leva + desna) / 2, desna, a);
        int l = leva, d = 1 + (leva + desna) / 2;
        while (l < d)
        {
            if (a [l] < a [d])
            {
                l++;
            }
            else
            {
                int p = a [l];
                a [l] = a [d];
                a [d] = p;
                l++;
                d++;
            }
        }
        FormirajBST (koren, leva, desna, a);
    }
    else
    {
        bstCvor koren;
        koren.vred = a [leva];
        koren.levimin = -1;
        koren.desnimax = -1;
        koren.levimax = -1;
        koren.desnimin = -1;
        koren.bPotL = 0;
        koren.bPotD = 0;
        cvorak.BST = koren;
    }
}

int n, q;
int niz [50000];

int main ()
{
    FILE *in = fopen ("pijaca.in", "r");
    FILE *out = fopen ("pijaca.out", "w");
    fscanf (in, "%d", &n);
    for (int i = 0; i < n; i++)
    {
        fscanf (in, "%d", &niz [i]);
    }
    fscanf (in, "%d", &q);
    if (q % 2 == 0)
    {
        fprintf (out, "2\n3");
    }
    else
    {
        segCvor korenSeg;
        FormirajSegmentno (korenSeg, 0, n - 1, niz);
        for (int i = 0; i < q; i++)
        {
            int l, r, a, b;
            //fscanf ();
        }
    }
    return 0;
}
