1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

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

#define pb push_back
#define mp make_pair
#define st first
#define nd second

int NC = 1;
struct Node {
  int left_child;
  int right_child;
  int in_order;
};
Node nodes[12000000];
vector<int> by_level[20];

int T[600000];
int create(int A, int B, int l) {
  by_level[l].pb(NC);
  Node& n = nodes[NC++];

  if (l == 0) {
    n.in_order = T[A];
  } else {
    n.left_child = create(A, (A+B)/2, l-1);
    n.right_child = create((A+B)/2, B, l-1);
  }
  return &n - nodes;
}

int replace(int n, int A, int B, int l, int pos, int value) {
  const Node& current_node = nodes[n];
  by_level[l].pb(NC);
  Node& new_node = nodes[NC++];

  if (A + 1 == B) {
    new_node.in_order = value;
  } else {
    if (pos < (A+B)/2) {
      new_node.left_child = replace(current_node.left_child, A, (A+B)/2, l-1,  pos, value);
      new_node.right_child = current_node.right_child;
    } else {
      new_node.left_child = current_node.left_child;
      new_node.right_child = replace(current_node.right_child, (A+B)/2, B, l-1, pos, value);
    }
  }

  return &new_node - nodes;
}

void print(int node, int level) {
  if (level == 0) printf("%d ", nodes[node].in_order);
  else {
    print(nodes[node].left_child, level-1);
    print(nodes[node].right_child, level-1);
  }
}

void sort_level(int level) {
  vector<pair<PII, int>> data;
  for (int n: by_level[level]) {
    data.pb({
      { nodes[nodes[n].left_child].in_order, nodes[nodes[n].right_child].in_order},
      n
    });
  }
  sort(data.begin(), data.end());

  PII cur = {-1, -1};
  int in_order = 0;
  for (auto p: data) {
    if (p.st != cur) {
      ++in_order;
      cur = p.st;
    }
    nodes[p.nd].in_order = in_order;
  }
}

int nodenum[1000000];

int main() {
  // ios_base::sync_with_stdio(0);

  int N, M;
  scanf("%d%d", &N, &M);
  REP(i,N) scanf("%d", &T[i]);

  int levels = 1;
  {
    int N2 = 1;
    while (N2 < N) {
      N2 <<= 1;
      ++levels;
    }
    N = N2;
  }

  nodenum[1] = create(0, N, levels-1);
  FOR(i,2,M+1) {
    int p, x;
    scanf("%d%d", &p, &x);
    nodenum[i] = replace(nodenum[i-1], 0, N, levels-1, p-1, x);
  }

  FOR(level,1,levels) {
    sort_level(level);
  }

  vector<PII> vec;
  FOR(i,1,M+1) vec.pb({nodes[nodenum[i]].in_order, i});
  sort(vec.begin(), vec.end());
  for (auto p: vec) printf("%d ", p.nd);
  printf("\n");
}