// Author: Gustav Matula
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long llint;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

const int inf = 1e9;
using Range = pair<int,int>;

struct Tournament {
  static const int off = 1 << 17;
  using Node = pair<int,int>;

  vector<Node> t;

  Tournament() {
    t.resize(2 * off, {+inf, -inf});
  }

  Node merge(const Node &l, const Node &r) {
    return { min(l.first, r.first), max(l.second, r.second) };
  }

  Node query(int l, int r, int lo = 0, int hi = off, int i = 1) {
    if (lo >= r || hi <= l) return {+inf, -inf};
    if (lo >= l && hi <= r) return t[i];
    int mid = (lo + hi) / 2;
    return merge(query(l, r, lo, mid, 2 * i),
		 query(l, r, mid, hi, 2 * i + 1));
  }
    
  int get_min(int l, int r) { return query(l, r).first; }
  int get_max(int l, int r) { return query(l, r).second; }
  int get(int i) { return t[i + off].first; }
    
  void set_min(int i, int v) { set(i, min(v, get(i))); }
  void set_max(int i, int v) { set(i, max(v, get(i))); }

  void set(int i, int v) {
    i += off;
    t[i].first = t[i].second = v;
    for (i /= 2; i; i /= 2) 
      t[i] = merge(t[2 * i], t[2 * i + 1]);
  }
};

Tournament inv;
vector<pair<int,int>> G;
set<int> living;
  
vector<int> dis, com;
Tournament low;
int tick;
stack<int> stk;

Tournament range_min;
Tournament range_max;

void dfs(int i) {
  ++tick;
  dis[i] = tick;
  low.set(i, tick);
  stk.push(i);

  low.set(i, min(tick, low.get_min(G[i].first, G[i].second)));

  vector<int> js;
  for (auto jt = living.lower_bound(G[i].first);
       jt != living.end() && *jt < G[i].second;
       ++jt) 
    js.push_back(*jt);

  for (int j : js) {
    living.erase(j);
    if (!dis[j]) dfs(j);
    low.set_min(i, low.get(j));
  }

  range_min.set_min(i, range_min.get_min(G[i].first, G[i].second));
  range_max.set_max(i, range_max.get_max(G[i].first, G[i].second));

  if (low.get(i) < dis[i]) return;

  vector<int> component;
  int lo = +inf, hi = -inf;

  for (;;) {
    int j = stk.top(); stk.pop();
    low.set(j, inf);
    component.push_back(j);
    lo = min(lo, range_min.get(j));
    hi = max(hi, range_max.get(j));
    if (j == i) break;
  }

  for (int j : component) {
    range_min.set_min(j, lo);
    range_max.set_max(j, hi);
  }
}


void solve(const vector<int> &p) {
  int n = p.size();
  REP(i, n) inv.set(p[i], i);

  REP(i, n - 1) {
    int l = p[i], r = p[i + 1];
    if (l > r) swap(l, r);

    int lo = inv.get_min(l, r + 1);
    int hi = inv.get_max(l, r + 1);

    G.push_back({lo, hi});
  }

  living.clear();
  REP(i, n - 1) living.insert(i);

  REP(i, (int)p.size() - 1) {
    range_min.set(i, G[i].first);
    range_max.set(i, G[i].second);
  }

  dis.resize(n, 0);
  com.resize(n, -1);
  REP(i, n) if (!dis[i]) dfs(i);
}

int main(void)
{
  int N;
  scanf("%d", &N);
  vector<int> p(N);
  REP(i, N) { scanf("%d", &p[i]); --p[i]; }

  solve(p);

  map<int,int> freq;

  int Q;
  scanf("%d", &Q);
  REP(i, Q) {
    int l, r;
    scanf("%d%d", &l, &r); --l; --r;
    if (l == r) {
      printf("%d %d\n", l + 1, r + 1);
    } else {
      int lo = range_min.get_min(l, r);
      int hi = range_max.get_max(l, r);
      printf("%d ", lo + 1);
      printf("%d\n", hi + 1);
    }
  }

  return 0;
}