#include <bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool isone(long long, int);
int count(long long);
long long exp(long long, long long, long long);
long long GCD(long long, long long);
struct node {
  int l, r;
  int idx;
} a[200010];
int ans[200010];
int BIT[2000010];
bool comp(const struct node &a, const struct node &b) { return a.r <= b.r; }
void update(int idx) {
  for (; idx < 2000010; idx += (idx & (-idx))) BIT[idx]++;
  return;
}
int freq(int idx) {
  int ret = 0;
  for (; idx > 0; idx -= (idx & (-idx))) ret += BIT[idx];
  return ret;
}
int main() {
  int n;
  scanf("%d", &n);
  vector<int> c;
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i].idx = i;
    a[i].l = x;
    a[i].r = y;
    c.push_back(a[i].l);
    c.push_back(a[i].r);
  }
  sort(c.begin(), c.end());
  map<int, int> d;
  for (int i = 0; i < c.size(); i++) d[c[i]] = i + 10;
  for (int i = 0; i < n; i++) {
    a[i].l = d[a[i].l];
    a[i].r = d[a[i].r];
  }
  sort(a, a + n, comp);
  for (int i = 0; i < n; i++) {
    int val = freq(a[i].l);
    ans[a[i].idx] = i - val;
    update(a[i].l);
  }
  for (int i = 0; i < n; i++) printf("%d ", ans[i]);
  return 0;
}
long long GCD(long long a, long long b) {
  if (!b)
    return a;
  else
    return GCD(b, a % b);
}
long long exp(long long a, long long b, long long c) {
  long long ret = 1LL;
  long long mult = a;
  while (b) {
    if (b & 1) ret = (ret * mult) % c;
    mult = (mult * mult) % c;
    b >>= 1;
  }
  return ret;
}
int count(long long x) {
  int ret = 0;
  while (x) {
    if (x & 1) ret++;
    x >>= 1LL;
  }
  return ret;
}
bool isone(long long x, int pos) { return x & (1 << pos); }

### 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 dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool isone(long long, int);
int count(long long);
long long exp(long long, long long, long long);
long long GCD(long long, long long);
struct node {
  int l, r;
  int idx;
} a[200010];
int ans[200010];
int BIT[2000010];
bool comp(const struct node &a, const struct node &b) { return a.r <= b.r; }
void update(int idx) {
  for (; idx < 2000010; idx += (idx & (-idx))) BIT[idx]++;
  return;
}
int freq(int idx) {
  int ret = 0;
  for (; idx > 0; idx -= (idx & (-idx))) ret += BIT[idx];
  return ret;
}
int main() {
  int n;
  scanf("%d", &n);
  vector<int> c;
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i].idx = i;
    a[i].l = x;
    a[i].r = y;
    c.push_back(a[i].l);
    c.push_back(a[i].r);
  }
  sort(c.begin(), c.end());
  map<int, int> d;
  for (int i = 0; i < c.size(); i++) d[c[i]] = i + 10;
  for (int i = 0; i < n; i++) {
    a[i].l = d[a[i].l];
    a[i].r = d[a[i].r];
  }
  sort(a, a + n, comp);
  for (int i = 0; i < n; i++) {
    int val = freq(a[i].l);
    ans[a[i].idx] = i - val;
    update(a[i].l);
  }
  for (int i = 0; i < n; i++) printf("%d ", ans[i]);
  return 0;
}
long long GCD(long long a, long long b) {
  if (!b)
    return a;
  else
    return GCD(b, a % b);
}
long long exp(long long a, long long b, long long c) {
  long long ret = 1LL;
  long long mult = a;
  while (b) {
    if (b & 1) ret = (ret * mult) % c;
    mult = (mult * mult) % c;
    b >>= 1;
  }
  return ret;
}
int count(long long x) {
  int ret = 0;
  while (x) {
    if (x & 1) ret++;
    x >>= 1LL;
  }
  return ret;
}
bool isone(long long x, int pos) { return x & (1 << pos); }

```