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
#include <cctype>
#include <cstdio>
#include <cassert>
#include <tuple>
#include <vector>
#include <numeric>
#include <algorithm>

const int N = 500000 + 10;

int nextInt() {
  char ch;
  while (!isdigit(ch = getchar())) {}
  int res = ch - '0';
  while (isdigit(ch = getchar())) res = 10 * res + ch - '0';
  return res;
}

int n, m, t[N];
std::tuple<int, int, int> info[N];

int rank[N], tot;

void calc(const std::vector<std::pair<int, int>> &a, const std::vector<std::pair<int, int>> &b, std::vector<std::tuple<int, int, int>> &res) {
  for (int i = 0, j = 0; i < a.size(); ++i) {
    while (j + 1 < b.size() && b[j + 1].first <= a[i].first) ++j;
    res.emplace_back(a[i].second, b[j].second, a[i].first);
  }
}

inline bool comp(const std::tuple<int, int, int> &lhs, const std::tuple<int, int, int> &rhs) {
  return std::get<2>(lhs) < std::get<2>(rhs);
}

void radixSort(std::vector<std::tuple<int, int, int>> &cur) {
  int x = 0, y = 0;
  for (const auto &it : cur) x = std::max(x, std::get<0>(it)), y = std::max(y, std::get<1>(it));
  static int sum[N];
  std::fill(sum, sum + y + 1, 0);
  static int id[N];
  for (const auto &it : cur) ++sum[std::get<1>(it)];
  for (int i = 1; i <= y; ++i) sum[i] += sum[i - 1];
  for (int i = 0; i < cur.size(); ++i) id[--sum[std::get<1>(cur[i])]] = i;
  std::fill(sum, sum + x + 1, 0);
  for (const auto &it : cur) ++sum[std::get<0>(it)];
  for (int i = 1; i <= x; ++i) sum[i] += sum[i - 1];
  static std::tuple<int, int, int> temp[N];
  for (int i = cur.size() - 1; i >= 0; --i) temp[--sum[std::get<0>(cur[id[i]])]] = cur[id[i]];
  std::copy(temp, temp + cur.size(), cur.begin());
}

int solve(int l, int r) {
  int u = std::get<0>(info[l]), v = std::get<0>(info[r]);
  if (u == v) {
    static std::vector<std::pair<int, int>> temp;
    temp.clear();
    temp.emplace_back(t[u], 0);
    for (int i = l; i <= r; ++i) temp.emplace_back(std::get<1>(info[i]), std::get<2>(info[i]));
    std::sort(temp.begin(), temp.end());
    for (int i = 0, k = 0; i < temp.size(); ++i) rank[temp[i].second] = (k += (!i || temp[i].first != temp[i - 1].first));
    std::sort(info + l, info + r + 1, comp);
    return rank[0];
  }
  int w = (u + v) / 2, mid = l;
  while (mid < r && std::get<0>(info[mid + 1]) <= w) ++mid;
  int p = solve(l, mid), q = solve(mid + 1, r);
  static std::vector<std::pair<int, int>> a, b;
  a.clear(), b.clear();
  a.emplace_back(0, p);
  b.emplace_back(0, q);
  for (int i = l; i <= mid; ++i) {
    int x = std::get<2>(info[i]);
    a.emplace_back(x, rank[x]);
  }
  for (int i = mid + 1; i <= r; ++i) {
    int x = std::get<2>(info[i]);
    b.emplace_back(x, rank[x]);
  }
  static std::vector<std::tuple<int, int, int>> cur;
  cur.clear();
  calc(a, b, cur);
  int temp = cur.size();
  calc(b, a, cur);
  for (int i = temp; i < cur.size(); ++i) std::swap(std::get<0>(cur[i]), std::get<1>(cur[i]));
  radixSort(cur);
  for (int i = 0, k = 0; i < cur.size(); ++i)
    rank[std::get<2>(cur[i])] = (k += (!i || std::get<0>(cur[i]) != std::get<0>(cur[i - 1]) || std::get<1>(cur[i]) != std::get<1>(cur[i - 1])));
  std::inplace_merge(info + l, info + mid + 1, info + r + 1, comp);
  return rank[0];
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) t[i] = nextInt();
  for (int i = 1; i < m; ++i) {
    int x = nextInt(), y = nextInt();
    info[i] = std::make_tuple(x, y, i);
  }
  std::sort(info + 1, info + m);
  solve(1, m - 1);
  static int ans[N];
  std::iota(ans, ans + m, 0);
  std::sort(ans, ans + m, [&] (int a, int b) { return std::tie(rank[a], a) < std::tie(rank[b], b); });
  for (int i = 0; i < m; ++i) printf("%d ", ans[i] + 1);
  return 0;
}