/* <O(n) - PreProc >
   <O(sqrt(n)) - Query >
*/
#define MAX 100005
#include<stdio.h>
int A[100005];
int a;
int b;
int Dq[100005];
int st,fn;
int M[5000];
int rp;
int N;
int min;
int j;
int contor2;
int contor;
int Q;
int rest(int a, int b)
{
    while (a >= b) a-= b;
    return a;
}
int main()
{
        freopen("rmq.in", "r", stdin);
        freopen("rmq.out", "w", stdout);

        scanf("%d %d",&N,&Q);
        for(int i = 1; i <= N; i++)
         scanf("%d",&A[i]);

        for(rp = 0; rp * rp <= N; rp++);
         rp--;
        Dq[++st] = 1;
        fn = st;

        for(int i = 2; i <= N; i++)
         {
             if (i > rp)
              {
                  if (A[i-rp] == A[Dq[st]]) st++;
              }
             while (A[Dq[fn]] >= A[i] && fn >= st) fn--;
             Dq[++fn] = i;
             if (rest(i, rp) == 0)
              M[contor++] = Dq[st];
         }
         int cat = N / rp;
         for(int j = N - rp + 1 ; j <= rp * cat; j++)
          if (A[Dq[st]] == A[j]) st++;
         M[contor++] = Dq[st];
        A[0] = MAX;

        for(int i = 1; i <= Q; i++)
         {
             scanf("%d %d",&a,&b);
             int min = 0;
             contor = rp - rest(a,rp);
             if (contor == rp) contor = 0;
             for(int j = a; j <= a + contor; j++)
              if  (A[min] > A[j]) min = j;
             contor2 = (a + contor) / rp;
             for( j = a + contor ; j + rp <= b; j += rp)
              {
                   if (A[M[contor2]] < A[min])
                    min = M[contor2];
                   contor2++;
              }
              while (j <= b)
              {
                  if (A[j] < A[min]) min = j;
                  j++;
              }

            printf("%d\n",A[min]);
         }
        return 0;

}