#include <fstream>

using namespace std;

ifstream cin ("rmq.in");
ofstream cout ("rmq.out");

const int max_size = 1e5 + 1, max_r = 17;

int a[max_size], st[max_size], rmin[max_r][max_size], rmax[max_r][max_size], frecv[max_size], lg[max_size];

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, j = 1, t;
    cin >> n >> t;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        frecv[a[i]]++;
        while (frecv[a[i]] == 2)
        {
            frecv[a[j]]--;
            j++;
        }
        st[i] = j;
    }
    lg[1] = 0;
    rmin[0][1] = rmax[0][1] = a[1];
    for (int i = 2; i <= n; i++)
    {
        lg[i] = lg[i / 2] + 1;
        rmin[0][i] = rmax[0][i] = a[i];
    }
    int l;
    for (int i = 1; (1 << i) <= n; i++)
    {
        for (int j = 1; j <= n - (1 << i) + 1; j++)
        {
            l = (1 << (i - 1));
            rmin[i][j] = min(rmin[i - 1][j], rmin[i - 1][j + l]);
            rmax[i][j] = max(rmax[i - 1][j], rmax[i - 1][j + l]);
        }
    }
    while (t--)
    {
        int x, y;
        cin >> x >> y;
        int diff = y - x + 1;
        l = lg[diff];
        int sh = diff - (1 << l);
        int min1 = min(rmin[l][x], rmin[l][x + sh]), max1 = max(rmax[l][x], rmax[l][x + sh]);
        cout << min1 << '\n';
    }
    return 0;
}