/* Rozwiazanie wzorcowe do zadania ZOL (Zolnierze)
 * Autor: Jakub Radoszewski
 * Opis: Implementacja na secie, czas O(nlogn)
 */

#include <cstdio>
#include <set>
#include <cassert>
using namespace std;

#define M 500010

int n;
int t[M], pozycja[M];
set<int> szereg;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    t[i] = i;
    pozycja[t[i]] = i;
  }
  for (int i = 0; i < n; ++i) szereg.insert(i);
  for (int q = 0; q < n; ++q) {
    int nr;
    scanf("%d", &nr);
    --nr;
    int poz = pozycja[nr];
    set<int>::iterator it = szereg.find(poz), it1;
    assert(it != szereg.end());
    if (it == szereg.begin()) printf("-1 ");
    else {
      it1 = it;
      --it1;
      printf("%d ", t[*it1] + 1);
    }
    it1 = it;
    ++it1;
    if (it1==szereg.end()) printf("-1\n"); else printf("%d\n", t[*it1] + 1);
    szereg.erase(it);
  }
  return 0;
}