#include <bits/stdc++.h>
using namespace std;
int tot;
int val[412345];
int n;
struct line {
  int l;
  int r;
  int id;
} L[212345];
struct point {
  int pos;
  int op;
  int id;
  point(){};
  point(int pos, int op, int id) : pos(pos), op(op), id(id){};
} P[212345 * 2];
bool cmp1(line A, line B) { return A.l < B.l; }
bool cmp2(point A, point B) { return A.pos < B.pos; }
void init() {
  sort(P + 1, P + 1 + tot, cmp2);
  int pos = 1;
  for (int i = 1; i <= tot; i++) {
    int id = P[i].id;
    int op = P[i].op;
    if (op == 1)
      L[id].l = pos++;
    else
      L[id].r = pos++;
  }
}
int lowbit(int k) { return k & (-k); }
void Update(int pos, int v) {
  for (int p = pos; p < 2 * n + 5; p += lowbit(p)) {
    val[p] += v;
  }
}
int Query(int pos) {
  int cnt = 0;
  for (int p = pos; p > 0; p -= lowbit(p)) {
    cnt += val[p];
  }
  return cnt;
}
int ans[212345];
void Compute() {
  memset(val, 0, sizeof val);
  for (int i = 1; i <= n; i++) {
    Update(L[i].r, 1);
  }
  for (int i = 1; i <= n; i++) {
    int id = L[i].id;
    ans[id] = Query(L[i].r - 1) - Query(L[i].l);
    Update(L[i].r, -1);
  }
  for (int i = 1; i <= n; i++) {
    printf("%d\n", ans[i]);
  }
}
int main() {
  tot = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &L[i].l, &L[i].r);
    L[i].id = i;
    P[++tot] = point(L[i].l, 1, i);
    P[++tot] = point(L[i].r, 0, i);
  }
  init();
  sort(L + 1, L + 1 + n, cmp1);
  Compute();
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 tot;
int val[412345];
int n;
struct line {
  int l;
  int r;
  int id;
} L[212345];
struct point {
  int pos;
  int op;
  int id;
  point(){};
  point(int pos, int op, int id) : pos(pos), op(op), id(id){};
} P[212345 * 2];
bool cmp1(line A, line B) { return A.l < B.l; }
bool cmp2(point A, point B) { return A.pos < B.pos; }
void init() {
  sort(P + 1, P + 1 + tot, cmp2);
  int pos = 1;
  for (int i = 1; i <= tot; i++) {
    int id = P[i].id;
    int op = P[i].op;
    if (op == 1)
      L[id].l = pos++;
    else
      L[id].r = pos++;
  }
}
int lowbit(int k) { return k & (-k); }
void Update(int pos, int v) {
  for (int p = pos; p < 2 * n + 5; p += lowbit(p)) {
    val[p] += v;
  }
}
int Query(int pos) {
  int cnt = 0;
  for (int p = pos; p > 0; p -= lowbit(p)) {
    cnt += val[p];
  }
  return cnt;
}
int ans[212345];
void Compute() {
  memset(val, 0, sizeof val);
  for (int i = 1; i <= n; i++) {
    Update(L[i].r, 1);
  }
  for (int i = 1; i <= n; i++) {
    int id = L[i].id;
    ans[id] = Query(L[i].r - 1) - Query(L[i].l);
    Update(L[i].r, -1);
  }
  for (int i = 1; i <= n; i++) {
    printf("%d\n", ans[i]);
  }
}
int main() {
  tot = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &L[i].l, &L[i].r);
    L[i].id = i;
    P[++tot] = point(L[i].l, 1, i);
    P[++tot] = point(L[i].r, 0, i);
  }
  init();
  sort(L + 1, L + 1 + n, cmp1);
  Compute();
  return 0;
}

```