#include <bits/stdc++.h>
using namespace std;
int arr[200000 + 5];
int BIT[200000 + 5];
int n;
int finalans[200000 + 5];
int order[200000 + 5];
int getNext(int i) { return i + (i & (-1 * i)); }
int getParent(int i) { return i - (i & (-1 * i)); }
void updateFenwick(int index) {
  BIT[index] += 1;
  int j = index;
  while (getNext(j) <= n) {
    j = getNext(j);
    BIT[j] += 1;
  }
}
int readFenwick(int index) {
  int ans = BIT[index];
  while (index != 0) {
    index = getParent(index);
    ans += BIT[index];
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  int i;
  cin >> n;
  pair<int, int> s;
  pair<int, int> r;
  pair<int, int> k;
  vector<pair<int, int> > seg;
  vector<pair<int, int> > e;
  vector<pair<int, int> > f;
  BIT[0] = 0;
  for (i = 1; i <= n; i++) {
    cin >> s.first >> s.second;
    seg.push_back(s);
    k.first = s.second;
    k.second = i;
    f.push_back(k);
    BIT[i] = 0;
  }
  sort(seg.begin(), seg.end());
  sort(f.begin(), f.end());
  for (i = 0; i < n; i++) {
    r.first = seg[i].second;
    r.second = i + 1;
    e.push_back(r);
  }
  sort(e.begin(), e.end());
  for (i = 0; i < n; i++) {
    arr[e[i].second] = i + 1;
    order[f[i].second] = i + 1;
  }
  for (i = n; i >= 1; i--) {
    finalans[arr[i]] = readFenwick(arr[i]);
    updateFenwick(arr[i]);
  }
  for (i = 1; i <= n; i++) cout << finalans[order[i]] << "\n";
  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;
int arr[200000 + 5];
int BIT[200000 + 5];
int n;
int finalans[200000 + 5];
int order[200000 + 5];
int getNext(int i) { return i + (i & (-1 * i)); }
int getParent(int i) { return i - (i & (-1 * i)); }
void updateFenwick(int index) {
  BIT[index] += 1;
  int j = index;
  while (getNext(j) <= n) {
    j = getNext(j);
    BIT[j] += 1;
  }
}
int readFenwick(int index) {
  int ans = BIT[index];
  while (index != 0) {
    index = getParent(index);
    ans += BIT[index];
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  int i;
  cin >> n;
  pair<int, int> s;
  pair<int, int> r;
  pair<int, int> k;
  vector<pair<int, int> > seg;
  vector<pair<int, int> > e;
  vector<pair<int, int> > f;
  BIT[0] = 0;
  for (i = 1; i <= n; i++) {
    cin >> s.first >> s.second;
    seg.push_back(s);
    k.first = s.second;
    k.second = i;
    f.push_back(k);
    BIT[i] = 0;
  }
  sort(seg.begin(), seg.end());
  sort(f.begin(), f.end());
  for (i = 0; i < n; i++) {
    r.first = seg[i].second;
    r.second = i + 1;
    e.push_back(r);
  }
  sort(e.begin(), e.end());
  for (i = 0; i < n; i++) {
    arr[e[i].second] = i + 1;
    order[f[i].second] = i + 1;
  }
  for (i = n; i >= 1; i--) {
    finalans[arr[i]] = readFenwick(arr[i]);
    updateFenwick(arr[i]);
  }
  for (i = 1; i <= n; i++) cout << finalans[order[i]] << "\n";
  return 0;
}

```