RC01 Solution

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#include <cstdio>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1009;

int a[N];
int ans[N][N];

int main () {
        int n; scanf ("%d", &n);
        for (int i = 0; i < n; i++) {
                scanf ("%d", &a[i]);
        }
        for (int i = 0; i < n; i++) {
                ordered_set s;
                for (int j = i; j < n; j++) {
                        s.insert (a[j]);
                        ans[i][j] = *s.find_by_order ((j - i) >> 1);
                }
        }
        int q; scanf ("%d", &q);
        while (q--) {
                int l, r; scanf ("%d%d", &l, &r);
                printf ("%d\n", ans[--l][--r]);
        }
}