#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int N = 1e5 + ;

int n , m;

int a[N] , rt[N];

struct Presitent_Segment_Tree

{

        int sz;

        int lc[N * ] , rc[N * ] , sum[N * ];

        Presitent_Segment_Tree()

        {

                sz = ;

        }

        inline void modify(int &now , int old , int l , int r , int x , int value)

        {

                now = ++sz;

                lc[now] = lc[old] , rc[now] = rc[old];

                sum[now] = sum[old] + value;

                if (l == r) return;

                int mid = (l + r) >> ;

                if (mid >= x) modify(lc[now] , lc[old] , l , mid , x , value);

                else modify(rc[now] , rc[old] , mid +  , r , x , value);

        }

        inline int query(int rt1 , int rt2 , int l , int r , int ql , int qr)

        {

                if (l == ql && r == qr)

                        return sum[rt1] - sum[rt2];

                int mid = (l + r) >> ;

                if (mid >= qr) return query(lc[rt1] , lc[rt2] , l , mid , ql , qr);

                else if (mid +  <= ql) return query(rc[rt1] , rc[rt2] , mid +  , r , ql , qr);

                else return query(lc[rt1] , lc[rt2] , l , mid , ql , mid) + query(rc[rt1] , rc[rt2] , mid +  , r , mid +  , qr);

        }

} PST;

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

int main()

{

        read(n);

        for (int i = ; i <= n; ++i) read(a[i]);

        for (int i = ; i <= n; ++i) PST.modify(rt[i] , rt[i - ] ,  , (int)1e9 , a[i] , a[i]);

        read(m);

        while (m--)

        {

                int l , r;

                read(l); read(r);

                 int ans =  , res = ;

                while (true)

                {

                        res = PST.query(rt[r] , rt[l - ] ,  , (int)1e9 ,  , ans);

                        if (res >= ans) ans = res + ;

                        else break;

                }

                printf("%d\n" , ans);

        }

        return ;

}