#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
  int x, y;
  int id;
} b[400005];
bool cmp(node a, node b) { return a.x > b.x; }
int res[400005];
int c[400005];
int lc[400005 * 30], rc[400005 * 30], a[400005 * 30];
int root = 1;
int tot = 1;
map<int, int> mp;
int query(int x, int l, int r, int tx, int ty) {
  if (x == 0) return 0;
  if (l >= tx && r <= ty) return a[x];
  int mid = (l + r) / 2;
  int ret = 0;
  if (mid >= tx) ret += query(lc[x], l, mid, tx, ty);
  if (mid < ty) ret += query(rc[x], mid + 1, r, tx, ty);
  return ret;
}
int add(int x, int l, int r, int wh) {
  if (x == 0) x = ++tot;
  a[x]++;
  if (l == r) return x;
  int mid = (l + r) / 2;
  if (mid >= wh) {
    lc[x] = add(lc[x], l, mid, wh);
  } else {
    rc[x] = add(rc[x], mid + 1, r, wh);
  }
  return x;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &b[i].x, &b[i].y), b[i].id = i;
    c[i] = b[i].y;
  }
  sort(c + 1, c + n + 1);
  for (int i = 1; i <= n; i++) {
    mp[c[i]] = i;
  }
  sort(b + 1, b + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    b[i].y = mp[b[i].y];
    res[b[i].id] = query(1, 1, 400005, 1, b[i].y);
    root = add(1, 1, 400005, b[i].y);
  }
  for (int i = 1; i <= n; i++) printf("%d\n", res[i]);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
int n;
struct node {
  int x, y;
  int id;
} b[400005];
bool cmp(node a, node b) { return a.x > b.x; }
int res[400005];
int c[400005];
int lc[400005 * 30], rc[400005 * 30], a[400005 * 30];
int root = 1;
int tot = 1;
map<int, int> mp;
int query(int x, int l, int r, int tx, int ty) {
  if (x == 0) return 0;
  if (l >= tx && r <= ty) return a[x];
  int mid = (l + r) / 2;
  int ret = 0;
  if (mid >= tx) ret += query(lc[x], l, mid, tx, ty);
  if (mid < ty) ret += query(rc[x], mid + 1, r, tx, ty);
  return ret;
}
int add(int x, int l, int r, int wh) {
  if (x == 0) x = ++tot;
  a[x]++;
  if (l == r) return x;
  int mid = (l + r) / 2;
  if (mid >= wh) {
    lc[x] = add(lc[x], l, mid, wh);
  } else {
    rc[x] = add(rc[x], mid + 1, r, wh);
  }
  return x;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &b[i].x, &b[i].y), b[i].id = i;
    c[i] = b[i].y;
  }
  sort(c + 1, c + n + 1);
  for (int i = 1; i <= n; i++) {
    mp[c[i]] = i;
  }
  sort(b + 1, b + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    b[i].y = mp[b[i].y];
    res[b[i].id] = query(1, 1, 400005, 1, b[i].y);
    root = add(1, 1, 400005, b[i].y);
  }
  for (int i = 1; i <= n; i++) printf("%d\n", res[i]);
  return 0;
}

```