#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 19;
struct Node {
  int l, r;
  int val;
  Node() : l(), r(), val() {}
  Node(int _l, int _r) : l(_l), r(_r), val() {}
};
Node tree[2 * N];
void build() {
  for (int i = 0; i < N; i++) tree[N + i] = Node(i, i + 1);
  for (int i = N - 1; i > 0; i--)
    tree[i] = Node(tree[2 * i].l, tree[2 * i + 1].r);
  return;
}
void addVal(int v) {
  v += N;
  tree[v].val++;
  while (v > 1) {
    v >>= 1;
    tree[v].val = tree[2 * v].val + tree[2 * v + 1].val;
  }
  return;
}
int getSum(int v, int l, int r) {
  if (l <= tree[v].l && tree[v].r <= r) return tree[v].val;
  if (l >= tree[v].r || tree[v].l >= r) return 0;
  return getSum(2 * v, l, r) + getSum(2 * v + 1, l, r);
}
int n;
pair<int, int> a[N];
pair<int, int> ev[N];
int m;
int xs[N];
int ans[N];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i] = make_pair(x, y);
    xs[2 * i] = x;
    xs[2 * i + 1] = y;
  }
  sort(xs, xs + 2 * n);
  for (int i = 0; i < n; i++) {
    int x = a[i].first, y = a[i].second;
    x = lower_bound(xs, xs + 2 * n, x) - xs;
    y = lower_bound(xs, xs + 2 * n, y) - xs;
    a[i] = make_pair(x, y);
    ev[m++] = make_pair(x, -i - 1);
    ev[m++] = make_pair(y, i + 1);
  }
  sort(ev, ev + m);
  build();
  for (int i = 0; i < m; i++) {
    int id = ev[i].second;
    if (id < 0) {
      id *= -1;
      id--;
      ans[id] -= getSum(1, 0, a[id].second);
      addVal(a[id].second);
    } else {
      id--;
      ans[id] += getSum(1, 0, a[id].second);
    }
  }
  for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Please create a solution in Cpp 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;
const int N = 1 << 19;
struct Node {
  int l, r;
  int val;
  Node() : l(), r(), val() {}
  Node(int _l, int _r) : l(_l), r(_r), val() {}
};
Node tree[2 * N];
void build() {
  for (int i = 0; i < N; i++) tree[N + i] = Node(i, i + 1);
  for (int i = N - 1; i > 0; i--)
    tree[i] = Node(tree[2 * i].l, tree[2 * i + 1].r);
  return;
}
void addVal(int v) {
  v += N;
  tree[v].val++;
  while (v > 1) {
    v >>= 1;
    tree[v].val = tree[2 * v].val + tree[2 * v + 1].val;
  }
  return;
}
int getSum(int v, int l, int r) {
  if (l <= tree[v].l && tree[v].r <= r) return tree[v].val;
  if (l >= tree[v].r || tree[v].l >= r) return 0;
  return getSum(2 * v, l, r) + getSum(2 * v + 1, l, r);
}
int n;
pair<int, int> a[N];
pair<int, int> ev[N];
int m;
int xs[N];
int ans[N];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i] = make_pair(x, y);
    xs[2 * i] = x;
    xs[2 * i + 1] = y;
  }
  sort(xs, xs + 2 * n);
  for (int i = 0; i < n; i++) {
    int x = a[i].first, y = a[i].second;
    x = lower_bound(xs, xs + 2 * n, x) - xs;
    y = lower_bound(xs, xs + 2 * n, y) - xs;
    a[i] = make_pair(x, y);
    ev[m++] = make_pair(x, -i - 1);
    ev[m++] = make_pair(y, i + 1);
  }
  sort(ev, ev + m);
  build();
  for (int i = 0; i < m; i++) {
    int id = ev[i].second;
    if (id < 0) {
      id *= -1;
      id--;
      ans[id] -= getSum(1, 0, a[id].second);
      addVal(a[id].second);
    } else {
      id--;
      ans[id] += getSum(1, 0, a[id].second);
    }
  }
  for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  return 0;
}

```