#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#define NMAX 100008

using namespace std;

int n, m;
struct node {
   int elem;
   node *p, *l, *r; /// parent left right
   node(int x, node *nod){
      elem = x;
      p = nod;
   }
   node(){}
};
map<int, node*> indexToNode;
int depth[NMAX];

void add(node *&last, int x)
{
   if (last->elem >= x){
      while (last->elem >= x)
         last = last->p;
      node *aux = new node(x, last);
      aux->l = last->r;
      last->r = aux;
      last = last->r;
      aux->l->p = aux;
   }
   else {
      last->r = new node(x, last);
      last = last->r;
   }
}

int lca(int x, int y) /// depth(x) > depth(y)
{
   int depX = depth[x];
   int depY = depth[y];
   node *nodeX = indexToNode[x];
   node *nodeY = indexToNode[y];
   while (depX != depY){
      depX--;
      nodeX = nodeX->p;
   }
   while (nodeX->elem != nodeY->elem){
      nodeX = nodeX->p;
      nodeY = nodeY->p;
   }
   return nodeX->elem;
}

int calcDepth(node *x)
{
   if (x->elem == 0){
      return 0;
   }
   return 1 + calcDepth(x->p);
}

int main()
{
   freopen("rmq.in", "r", stdin);
   freopen("rmq.out", "w", stdout);
   scanf("%d %d\n", &n, &m);
   int x, y;
   node *last = new node;
   last->elem = 0;
   for (int i = 1; i <= n; ++i){
      scanf("%d\n", &x);
      /// adaug elem in cartesian tree
      add(last, x);
      indexToNode.insert(make_pair(i, last));
   }
   for (int i = 1; i <= n; ++i)
      depth[i] = calcDepth(indexToNode[i]);
   for (int i = 1; i <= m; ++i){
      scanf("%d %d\n", &x, &y);
      printf("%d\n", (depth[x] >= depth[y])?lca(x, y):lca(y, x));
   }

   return 0;
}