#include <bits/stdc++.h>
using namespace std;
void FastIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  cout.precision(15);
}
class segment_tree {
 public:
  vector<int> ST;
  vector<int> A;
  int n;
  void build(int node, int l, int r) {
    if (l == r - 1) {
      ST[node] = A[l];
      return;
    }
    int leftChild = node << 1;
    int rightChild = leftChild | 1;
    int mid = (l + r) >> 1;
    build(leftChild, l, mid);
    build(rightChild, mid, r);
    int lc = ST[leftChild];
    int rc = ST[rightChild];
    ST[node] = lc + rc;
  }
  void update(int node, int l, int r, int idx, int x) {
    if (l == r - 1) {
      if (l == idx) ST[node] = x;
      return;
    }
    int leftChild = node << 1;
    int rightChild = leftChild | 1;
    int mid = (l + r) >> 1;
    if (idx < mid)
      update(leftChild, l, mid, idx, x);
    else
      update(rightChild, mid, r, idx, x);
    ST[node] = ST[leftChild] + ST[rightChild];
  }
  int range_query(int L, int R, int node, int l, int r) {
    if (l >= R || r <= L) return 0;
    int leftChild = node << 1;
    int rightChild = leftChild | 1;
    if (L <= l && r <= R) return ST[node];
    int mid = (l + r) >> 1;
    int leftAns = range_query(L, R, leftChild, l, mid);
    int rightAns = range_query(L, R, rightChild, mid, r);
    return leftAns + rightAns;
  }
  segment_tree() {
    ST.clear();
    A.clear();
    n = 0;
  }
  segment_tree(vector<int> &baseArray) {
    A = baseArray;
    n = (int)(baseArray.size());
    ST = vector<int>(4 * n, 0);
    build(1, 0, n);
  }
  segment_tree(int *begin, int *end) {
    A = vector<int>(begin, end);
    n = (int)(A.size());
    ST = vector<int>(4 * n, 0);
    build(1, 0, n);
  }
  int query(int L, int R) { return range_query(L, R, 1, 0, n); }
};
int main() {
  FastIO();
  int i, n, a, b, counter = 0, j;
  vector<pair<pair<int, int>, int> > vec;
  vector<int> v, ans;
  set<int> s;
  set<int>::iterator it;
  map<int, int> mp;
  cin >> n;
  ans.resize(n, 0);
  for (i = 0; i < n; i++) {
    cin >> a >> b;
    vec.push_back(make_pair(make_pair(b, a), i));
    s.insert(a);
  }
  sort(vec.begin(), vec.end());
  it = s.begin();
  while (it != s.end()) {
    mp[*it] = counter;
    it++;
    counter++;
  }
  vector<int> arr;
  arr.resize(counter, 0);
  segment_tree s1;
  s1 = segment_tree(arr);
  for (i = 0; i < n; i++) {
    a = vec[i].first.second;
    b = vec[i].first.first;
    ans[vec[i].second] = s1.query(mp[a] + 1, counter);
    s1.update(1, 0, counter, mp[a], 1);
  }
  for (i = 0; i < n; i++) cout << ans[i] << "\n";
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
void FastIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  cout.precision(15);
}
class segment_tree {
 public:
  vector<int> ST;
  vector<int> A;
  int n;
  void build(int node, int l, int r) {
    if (l == r - 1) {
      ST[node] = A[l];
      return;
    }
    int leftChild = node << 1;
    int rightChild = leftChild | 1;
    int mid = (l + r) >> 1;
    build(leftChild, l, mid);
    build(rightChild, mid, r);
    int lc = ST[leftChild];
    int rc = ST[rightChild];
    ST[node] = lc + rc;
  }
  void update(int node, int l, int r, int idx, int x) {
    if (l == r - 1) {
      if (l == idx) ST[node] = x;
      return;
    }
    int leftChild = node << 1;
    int rightChild = leftChild | 1;
    int mid = (l + r) >> 1;
    if (idx < mid)
      update(leftChild, l, mid, idx, x);
    else
      update(rightChild, mid, r, idx, x);
    ST[node] = ST[leftChild] + ST[rightChild];
  }
  int range_query(int L, int R, int node, int l, int r) {
    if (l >= R || r <= L) return 0;
    int leftChild = node << 1;
    int rightChild = leftChild | 1;
    if (L <= l && r <= R) return ST[node];
    int mid = (l + r) >> 1;
    int leftAns = range_query(L, R, leftChild, l, mid);
    int rightAns = range_query(L, R, rightChild, mid, r);
    return leftAns + rightAns;
  }
  segment_tree() {
    ST.clear();
    A.clear();
    n = 0;
  }
  segment_tree(vector<int> &baseArray) {
    A = baseArray;
    n = (int)(baseArray.size());
    ST = vector<int>(4 * n, 0);
    build(1, 0, n);
  }
  segment_tree(int *begin, int *end) {
    A = vector<int>(begin, end);
    n = (int)(A.size());
    ST = vector<int>(4 * n, 0);
    build(1, 0, n);
  }
  int query(int L, int R) { return range_query(L, R, 1, 0, n); }
};
int main() {
  FastIO();
  int i, n, a, b, counter = 0, j;
  vector<pair<pair<int, int>, int> > vec;
  vector<int> v, ans;
  set<int> s;
  set<int>::iterator it;
  map<int, int> mp;
  cin >> n;
  ans.resize(n, 0);
  for (i = 0; i < n; i++) {
    cin >> a >> b;
    vec.push_back(make_pair(make_pair(b, a), i));
    s.insert(a);
  }
  sort(vec.begin(), vec.end());
  it = s.begin();
  while (it != s.end()) {
    mp[*it] = counter;
    it++;
    counter++;
  }
  vector<int> arr;
  arr.resize(counter, 0);
  segment_tree s1;
  s1 = segment_tree(arr);
  for (i = 0; i < n; i++) {
    a = vec[i].first.second;
    b = vec[i].first.first;
    ans[vec[i].second] = s1.query(mp[a] + 1, counter);
    s1.update(1, 0, counter, mp[a], 1);
  }
  for (i = 0; i < n; i++) cout << ans[i] << "\n";
  return 0;
}

```