#include <bits/stdc++.h>
using namespace std;
struct date {
  int x, y, pos;
};
int n, sol;
int s1[200010];
vector<date> arb[4 * 200010];
date t[200010];
bool cmp(const date &a, const date &b) { return (a.x < b.x); }
void build(int nod, int st, int dr) {
  if (st == dr) {
    arb[nod].resize(1);
    arb[nod][0] = t[st];
    return;
  } else {
    int m = (st + dr) / 2;
    build(nod * 2, st, m);
    build(nod * 2 + 1, m + 1, dr);
    arb[nod].resize(dr - st + 1);
    int i = 0, j = 0, nr = -1;
    while (i < arb[nod * 2].size() && j < arb[nod * 2 + 1].size()) {
      if (arb[nod * 2][i].y < arb[nod * 2 + 1][j].y)
        nr++, arb[nod][nr] = arb[nod * 2][i], i++;
      else
        nr++, arb[nod][nr] = arb[nod * 2 + 1][j], j++;
    }
    while (i < arb[nod * 2].size()) {
      nr++;
      arb[nod][nr] = arb[nod * 2][i];
      i++;
    }
    while (j < arb[nod * 2 + 1].size()) {
      nr++;
      arb[nod][nr] = arb[nod * 2 + 1][j];
      j++;
    }
  }
}
int binary_searchx1(int st, int dr, int val) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (t[m].x >= val) {
      sol = m;
      dr = m - 1;
    } else
      st = m + 1;
  }
  return sol;
}
int binary_searchx2(int st, int dr, int val) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (t[m].x <= val) {
      sol = m;
      st = m + 1;
    } else
      dr = m - 1;
  }
  return sol;
}
int binary_searchy1(int st, int dr, int val, vector<date> &v) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (v[m - 1].y >= val) {
      sol = m;
      dr = m - 1;
    } else
      st = m + 1;
  }
  return sol;
}
int binary_searchy2(int st, int dr, int val, vector<date> &v) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (v[m - 1].y <= val) {
      sol = m;
      st = m + 1;
    } else
      dr = m - 1;
  }
  return sol;
}
void query(int nod, int st, int dr, int x, int y, int b) {
  if (st >= x && dr <= y) {
    int ly = binary_searchy1(1, arb[nod].size(), t[b].x, arb[nod]);
    int ry = binary_searchy2(1, arb[nod].size(), t[b].y, arb[nod]);
    if (ly != -1 && ly <= ry) sol = sol + (ry - ly + 1);
    return;
  } else {
    int m = (st + dr) / 2;
    if (x <= m) query(nod * 2, st, m, x, y, b);
    if (y > m) query(nod * 2 + 1, m + 1, dr, x, y, b);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d %d", &t[i].x, &t[i].y), t[i].pos = i;
  sort(t + 1, t + n + 1, cmp);
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int lx = binary_searchx1(1, n, t[i].x);
    int rx = binary_searchx2(1, n, t[i].y);
    sol = 0;
    query(1, 1, n, lx, rx, i);
    s1[t[i].pos] = sol - 1;
  }
  for (int i = 1; i <= n; i++) printf("%d\n", s1[i]);
  return 0;
}

### Prompt

Create a solution in cpp for 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 date {
  int x, y, pos;
};
int n, sol;
int s1[200010];
vector<date> arb[4 * 200010];
date t[200010];
bool cmp(const date &a, const date &b) { return (a.x < b.x); }
void build(int nod, int st, int dr) {
  if (st == dr) {
    arb[nod].resize(1);
    arb[nod][0] = t[st];
    return;
  } else {
    int m = (st + dr) / 2;
    build(nod * 2, st, m);
    build(nod * 2 + 1, m + 1, dr);
    arb[nod].resize(dr - st + 1);
    int i = 0, j = 0, nr = -1;
    while (i < arb[nod * 2].size() && j < arb[nod * 2 + 1].size()) {
      if (arb[nod * 2][i].y < arb[nod * 2 + 1][j].y)
        nr++, arb[nod][nr] = arb[nod * 2][i], i++;
      else
        nr++, arb[nod][nr] = arb[nod * 2 + 1][j], j++;
    }
    while (i < arb[nod * 2].size()) {
      nr++;
      arb[nod][nr] = arb[nod * 2][i];
      i++;
    }
    while (j < arb[nod * 2 + 1].size()) {
      nr++;
      arb[nod][nr] = arb[nod * 2 + 1][j];
      j++;
    }
  }
}
int binary_searchx1(int st, int dr, int val) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (t[m].x >= val) {
      sol = m;
      dr = m - 1;
    } else
      st = m + 1;
  }
  return sol;
}
int binary_searchx2(int st, int dr, int val) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (t[m].x <= val) {
      sol = m;
      st = m + 1;
    } else
      dr = m - 1;
  }
  return sol;
}
int binary_searchy1(int st, int dr, int val, vector<date> &v) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (v[m - 1].y >= val) {
      sol = m;
      dr = m - 1;
    } else
      st = m + 1;
  }
  return sol;
}
int binary_searchy2(int st, int dr, int val, vector<date> &v) {
  int sol = -1;
  while (st <= dr) {
    int m = (st + dr) / 2;
    if (v[m - 1].y <= val) {
      sol = m;
      st = m + 1;
    } else
      dr = m - 1;
  }
  return sol;
}
void query(int nod, int st, int dr, int x, int y, int b) {
  if (st >= x && dr <= y) {
    int ly = binary_searchy1(1, arb[nod].size(), t[b].x, arb[nod]);
    int ry = binary_searchy2(1, arb[nod].size(), t[b].y, arb[nod]);
    if (ly != -1 && ly <= ry) sol = sol + (ry - ly + 1);
    return;
  } else {
    int m = (st + dr) / 2;
    if (x <= m) query(nod * 2, st, m, x, y, b);
    if (y > m) query(nod * 2 + 1, m + 1, dr, x, y, b);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d %d", &t[i].x, &t[i].y), t[i].pos = i;
  sort(t + 1, t + n + 1, cmp);
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int lx = binary_searchx1(1, n, t[i].x);
    int rx = binary_searchx2(1, n, t[i].y);
    sol = 0;
    query(1, 1, n, lx, rx, i);
    s1[t[i].pos] = sol - 1;
  }
  for (int i = 1; i <= n; i++) printf("%d\n", s1[i]);
  return 0;
}

```