#include <bits/stdc++.h>
using namespace std;
char buff[10000];
int poz = 0;
void cit(int &numar) {
  numar = 0;
  char semn = '+';
  while (buff[poz] < '0' || buff[poz] > '9') {
    semn = buff[poz];
    if (++poz == 10000) fread(buff, 1, 10000, stdin), poz = 0;
  }
  while ('0' <= buff[poz] && buff[poz] <= '9') {
    numar = numar * 10 + buff[poz] - '0';
    if (++poz == 10000) fread(buff, 1, 10000, stdin), poz = 0;
  }
  if (semn == '-') numar = -numar;
}
ifstream f("d.in");
ofstream g("d.out");
struct info3 {
  int x, y, ind;
};
info3 a[200001], b[200001];
int TR[262150], ans[200001];
int n, s;
bool cmp(info3 x, info3 y) { return (x.x < y.x); }
bool cmp2(info3 x, info3 y) { return (x.y < y.y); }
void update(int node, int left, int right, int x, int val) {
  if (left > x || right < x) return;
  if (left == x && right == x) {
    TR[node] = val;
    return;
  }
  int mid = (left + right) / 2;
  update(2 * node, left, mid, x, val);
  update(2 * node + 1, mid + 1, right, x, val);
  TR[node] = TR[2 * node] + TR[2 * node + 1];
}
void query(int node, int left, int right, int a, int b) {
  if (left > b || right < a) return;
  if (a <= left && right <= b) {
    s += TR[node];
    return;
  }
  int mid = (left + right) / 2;
  query(2 * node, left, mid, a, b);
  query(2 * node + 1, mid + 1, right, a, b);
}
int cautbin(int lo, int hi, int x) {
  int mid;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (b[mid].y == x && b[mid - 1].y < x)
      return mid;
    else if (b[mid].y >= x)
      hi = mid - 1;
    else if (b[mid].y < x)
      lo = mid + 1;
  }
  return 0;
}
void normalize(info3 a[200001]) {
  b[0].y = -1000000001;
  for (int i = 1; i <= n; ++i) {
    b[i] = a[i];
  }
  sort(b + 1, b + 1 + n, cmp2);
  for (int i = 1; i <= n; ++i) {
    a[i].y = cautbin(1, n, a[i].y);
  }
}
int main() {
  cit(n);
  for (int i = 1; i <= n; ++i) {
    cit(a[i].x);
    cit(a[i].y);
    a[i].ind = i;
  }
  sort(a + 1, a + 1 + n, cmp);
  normalize(a);
  for (int i = 1; i <= n; ++i) {
    update(1, 1, n, a[i].y, 1);
  }
  for (int i = 1; i <= n; ++i) {
    s = 0;
    query(1, 1, n, 1, a[i].y);
    update(1, 1, n, a[i].y, 0);
    ans[a[i].ind] = s - 1;
  }
  for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
char buff[10000];
int poz = 0;
void cit(int &numar) {
  numar = 0;
  char semn = '+';
  while (buff[poz] < '0' || buff[poz] > '9') {
    semn = buff[poz];
    if (++poz == 10000) fread(buff, 1, 10000, stdin), poz = 0;
  }
  while ('0' <= buff[poz] && buff[poz] <= '9') {
    numar = numar * 10 + buff[poz] - '0';
    if (++poz == 10000) fread(buff, 1, 10000, stdin), poz = 0;
  }
  if (semn == '-') numar = -numar;
}
ifstream f("d.in");
ofstream g("d.out");
struct info3 {
  int x, y, ind;
};
info3 a[200001], b[200001];
int TR[262150], ans[200001];
int n, s;
bool cmp(info3 x, info3 y) { return (x.x < y.x); }
bool cmp2(info3 x, info3 y) { return (x.y < y.y); }
void update(int node, int left, int right, int x, int val) {
  if (left > x || right < x) return;
  if (left == x && right == x) {
    TR[node] = val;
    return;
  }
  int mid = (left + right) / 2;
  update(2 * node, left, mid, x, val);
  update(2 * node + 1, mid + 1, right, x, val);
  TR[node] = TR[2 * node] + TR[2 * node + 1];
}
void query(int node, int left, int right, int a, int b) {
  if (left > b || right < a) return;
  if (a <= left && right <= b) {
    s += TR[node];
    return;
  }
  int mid = (left + right) / 2;
  query(2 * node, left, mid, a, b);
  query(2 * node + 1, mid + 1, right, a, b);
}
int cautbin(int lo, int hi, int x) {
  int mid;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (b[mid].y == x && b[mid - 1].y < x)
      return mid;
    else if (b[mid].y >= x)
      hi = mid - 1;
    else if (b[mid].y < x)
      lo = mid + 1;
  }
  return 0;
}
void normalize(info3 a[200001]) {
  b[0].y = -1000000001;
  for (int i = 1; i <= n; ++i) {
    b[i] = a[i];
  }
  sort(b + 1, b + 1 + n, cmp2);
  for (int i = 1; i <= n; ++i) {
    a[i].y = cautbin(1, n, a[i].y);
  }
}
int main() {
  cit(n);
  for (int i = 1; i <= n; ++i) {
    cit(a[i].x);
    cit(a[i].y);
    a[i].ind = i;
  }
  sort(a + 1, a + 1 + n, cmp);
  normalize(a);
  for (int i = 1; i <= n; ++i) {
    update(1, 1, n, a[i].y, 1);
  }
  for (int i = 1; i <= n; ++i) {
    s = 0;
    query(1, 1, n, 1, a[i].y);
    update(1, 1, n, a[i].y, 0);
    ans[a[i].ind] = s - 1;
  }
  for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
  return 0;
}

```