#include <bits/stdc++.h>
using namespace std;
struct segment {
  int l, r, id;
} num[200005];
int ans[200005];
int ank[200005];
int segmentTree[200005 * 4];
map<int, int> Map;
int n;
bool cmp(segment x, segment y) {
  if (x.l == y.l) return x.r < y.r;
  return x.l < y.l;
}
void makeTree(int root, int left, int right) {
  if (left == right) {
    segmentTree[root] = 0;
    return;
  }
  int mid = (left + right) / 2;
  makeTree(root * 2, left, mid);
  makeTree(root * 2 + 1, mid + 1, right);
  segmentTree[root] = 0;
}
void add(int root, int left, int right, int dir) {
  if (left == right) {
    if (left == dir) segmentTree[root]++;
    return;
  }
  if (left > dir || right < dir) return;
  int mid = (left + right) / 2;
  add(root * 2, left, mid, dir);
  add(root * 2 + 1, mid + 1, right, dir);
  segmentTree[root] = segmentTree[root * 2] + segmentTree[root * 2 + 1];
}
int find(int root, int left, int right, int qleft, int qright) {
  if (left > qright || right < qleft) return 0;
  if (left >= qleft && right <= qright) return segmentTree[root];
  int mid = (left + right) / 2;
  return find(root * 2, left, mid, qleft, qright) +
         find(root * 2 + 1, mid + 1, right, qleft, qright);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    num[i].id = i;
    scanf("%d%d", &num[i].l, &num[i].r);
    ank[i] = num[i].r;
  }
  sort(ank + 1, ank + 1 + n);
  Map.clear();
  int now = -1000000005;
  int id = 0;
  for (int i = 1; i <= n; i++) {
    if (now == ank[i])
      continue;
    else {
      Map[ank[i]] = ++id;
      now = ank[i];
    }
  }
  sort(num + 1, num + 1 + n, cmp);
  ans[num[n].id] = 0;
  makeTree(1, 1, id);
  add(1, 1, id, Map[num[n].r]);
  for (int i = n - 1; i >= 1; i--) {
    int sum = find(1, 1, id, 1, Map[num[i].r]);
    ans[num[i].id] = sum;
    add(1, 1, id, Map[num[i].r]);
  }
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.

Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.

Output

Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.

Examples

Input

4
1 8
2 3
4 7
5 6


Output

3
0
1
0


Input

3
3 4
1 5
2 6


Output

0
1
1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct segment {
  int l, r, id;
} num[200005];
int ans[200005];
int ank[200005];
int segmentTree[200005 * 4];
map<int, int> Map;
int n;
bool cmp(segment x, segment y) {
  if (x.l == y.l) return x.r < y.r;
  return x.l < y.l;
}
void makeTree(int root, int left, int right) {
  if (left == right) {
    segmentTree[root] = 0;
    return;
  }
  int mid = (left + right) / 2;
  makeTree(root * 2, left, mid);
  makeTree(root * 2 + 1, mid + 1, right);
  segmentTree[root] = 0;
}
void add(int root, int left, int right, int dir) {
  if (left == right) {
    if (left == dir) segmentTree[root]++;
    return;
  }
  if (left > dir || right < dir) return;
  int mid = (left + right) / 2;
  add(root * 2, left, mid, dir);
  add(root * 2 + 1, mid + 1, right, dir);
  segmentTree[root] = segmentTree[root * 2] + segmentTree[root * 2 + 1];
}
int find(int root, int left, int right, int qleft, int qright) {
  if (left > qright || right < qleft) return 0;
  if (left >= qleft && right <= qright) return segmentTree[root];
  int mid = (left + right) / 2;
  return find(root * 2, left, mid, qleft, qright) +
         find(root * 2 + 1, mid + 1, right, qleft, qright);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    num[i].id = i;
    scanf("%d%d", &num[i].l, &num[i].r);
    ank[i] = num[i].r;
  }
  sort(ank + 1, ank + 1 + n);
  Map.clear();
  int now = -1000000005;
  int id = 0;
  for (int i = 1; i <= n; i++) {
    if (now == ank[i])
      continue;
    else {
      Map[ank[i]] = ++id;
      now = ank[i];
    }
  }
  sort(num + 1, num + 1 + n, cmp);
  ans[num[n].id] = 0;
  makeTree(1, 1, id);
  add(1, 1, id, Map[num[n].r]);
  for (int i = n - 1; i >= 1; i--) {
    int sum = find(1, 1, id, 1, Map[num[i].r]);
    ans[num[i].id] = sum;
    add(1, 1, id, Map[num[i].r]);
  }
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  return 0;
}

```