#include <cstdio>
#include <cmath>

#define LOGMAX 18
#define NMAX 100005

using namespace std;

int n,m,a,b,val;
int best[NMAX][LOGMAX];

int main()
{
   freopen("rmq.in","r",stdin);
   freopen("rmq.out","w",stdout);

   scanf("%d %d",&n,&m);
   for (int i=1;i<=n;i++)
   {
       scanf("%d",&val);
       best[i][0]=val;
   }
   for (int i=1;i<=17;i++)
    for (int j=1;j<=n;j++)
     best[j][i]=(best[j][i-1]<best[j+(1<<(i-1))][i-1]?best[j][i-1]:best[j+(1<<(i-1))][i-1]);
   for (int i=0;i<=1;i++)
    {
        for (int j=1;j<=n;j++)
         printf("%d ",best[j][i]);
        printf("\n");
    }
   for (int i=1;i<=m;i++)
    {
          scanf("%d %d",&a,&b);
         int lung=log2(b-a+1);
         printf("%d\n",best[a][lung]<best[b-(1<<lung-1)][lung]?best[a][lung]:best[b-(1<<lung-1)][lung]);
    }
   fclose(stdin);
   fclose(stdout);
}