#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-20;
const int intINF = 0x3f3f3f3f;
const long long SZ = 200010, SSZ = 1000010, APB = 26, one = 93,
                INF = 0x7fffffffffffffff, mod = 1000000007;
int n, ans[SZ], sum[SZ];
struct nd {
  int ll, rr, id;
  nd(int a = 0, int b = 0, int c = 0) : ll(a), rr(b), id(c) {}
  bool operator<(const nd& rbs) const { return ll < rbs.ll; }
};
nd arr[SZ];
void update(int x, int delta) {
  for (; x < SZ; x += x & -x) {
    sum[x] += delta;
  }
}
int qry(int x) {
  int res = 0;
  for (; x; x -= x & -x) {
    res += sum[x];
  }
  return res;
}
void init() {
  cin >> n;
  vector<int> ls;
  for (int i = 1; i <= n; ++i) {
    int a, b;
    cin >> a >> b;
    ls.push_back(b);
    arr[i] = nd(a, b, i);
  }
  sort(ls.begin(), ls.end());
  ls.erase(unique(ls.begin(), ls.end()), ls.end());
  sort(arr + 1, arr + 1 + n);
  for (int i = n; i >= 1; --i) {
    int pos = lower_bound(ls.begin(), ls.end(), arr[i].rr) - ls.begin() + 1;
    ans[arr[i].id] = qry(pos);
    update(pos, 1);
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i] << endl;
  }
}
void work() {}
int main() {
  std::ios::sync_with_stdio(0);
  int casenum;
  {
    init();
    work();
  }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution 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 double EPS = 1e-20;
const int intINF = 0x3f3f3f3f;
const long long SZ = 200010, SSZ = 1000010, APB = 26, one = 93,
                INF = 0x7fffffffffffffff, mod = 1000000007;
int n, ans[SZ], sum[SZ];
struct nd {
  int ll, rr, id;
  nd(int a = 0, int b = 0, int c = 0) : ll(a), rr(b), id(c) {}
  bool operator<(const nd& rbs) const { return ll < rbs.ll; }
};
nd arr[SZ];
void update(int x, int delta) {
  for (; x < SZ; x += x & -x) {
    sum[x] += delta;
  }
}
int qry(int x) {
  int res = 0;
  for (; x; x -= x & -x) {
    res += sum[x];
  }
  return res;
}
void init() {
  cin >> n;
  vector<int> ls;
  for (int i = 1; i <= n; ++i) {
    int a, b;
    cin >> a >> b;
    ls.push_back(b);
    arr[i] = nd(a, b, i);
  }
  sort(ls.begin(), ls.end());
  ls.erase(unique(ls.begin(), ls.end()), ls.end());
  sort(arr + 1, arr + 1 + n);
  for (int i = n; i >= 1; --i) {
    int pos = lower_bound(ls.begin(), ls.end(), arr[i].rr) - ls.begin() + 1;
    ans[arr[i].id] = qry(pos);
    update(pos, 1);
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i] << endl;
  }
}
void work() {}
int main() {
  std::ios::sync_with_stdio(0);
  int casenum;
  {
    init();
    work();
  }
  return 0;
}

```