#include <bits/stdc++.h>
using namespace std;
int64_t getMid(int64_t s, int64_t e) { return s + (e - s) / 2; }
bool compareTuple(tuple<int64_t, int64_t, int> a,
                  tuple<int64_t, int64_t, int> b) {
  return get<1>(a) > get<1>(b);
}
int64_t constructSTUtil(int64_t arr[], int64_t ss, int64_t se, int64_t *st,
                        int64_t si) {
  if (ss == se) {
    st[si] = arr[ss];
    return arr[ss];
  }
  int64_t mid = getMid(ss, se);
  st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) +
           constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);
  return st[si];
}
int64_t *constructST(int64_t arr[], int64_t n) {
  int64_t x = (int64_t)(ceil(log2(n)));
  int64_t max_size = 2 * (int64_t)pow(2, x) - 1;
  int64_t *st = new int64_t[max_size];
  constructSTUtil(arr, 0, n - 1, st, 0);
  return st;
}
int64_t getSumUtil(int64_t *st, int64_t ss, int64_t se, int64_t qs, int64_t qe,
                   int64_t si) {
  if (qs <= ss && qe >= se) return st[si];
  if (se < qs || ss > qe) return 0;
  int64_t mid = getMid(ss, se);
  return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) +
         getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);
}
int64_t getSum(int64_t *st, int64_t n, int64_t qs, int64_t qe) {
  if (qs < 0 || qe > n || qs > qe) {
    cout << "Invalid Input";
    return -1;
  }
  return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
void updateValueUtil(int64_t *st, int64_t ss, int64_t se, int64_t i,
                     int64_t diff, int64_t si) {
  if (i < ss || i > se) return;
  st[si] = st[si] + diff;
  if (se != ss) {
    int64_t mid = getMid(ss, se);
    updateValueUtil(st, ss, mid, i, diff, 2 * si + 1);
    updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2);
  }
}
void updateValue(int64_t arr[], int64_t *st, int64_t n, int64_t i,
                 int64_t new_val) {
  if (i < 0 || i > n - 1) {
    cout << "Invalid Input";
    return;
  }
  int64_t diff = new_val - arr[i];
  arr[i] = new_val;
  updateValueUtil(st, 0, n - 1, i, diff, 0);
}
int main() {
  int n = 0;
  cin >> n;
  vector<tuple<int64_t, int64_t, int>> vect;
  vector<int> values;
  int size = 2 * n;
  for (int i = 0; i < n; i++) {
    int64_t l, r = 0;
    cin >> l;
    cin >> r;
    values.push_back(l);
    values.push_back(r);
    tuple<int64_t, int64_t, int> tmp = make_tuple(l, r, i);
    vect.push_back(tmp);
  }
  std::sort(values.begin(), values.end());
  for (int i = 0; i < n; i++) {
    get<0>(vect[i]) =
        std::lower_bound(values.begin(), values.end(), get<0>(vect[i])) -
        values.begin();
    get<1>(vect[i]) =
        std::lower_bound(values.begin(), values.end(), get<1>(vect[i])) -
        values.begin();
  }
  std::sort(vect.begin(), vect.end(), compareTuple);
  int64_t *arr = (int64_t *)malloc(sizeof(int64_t) * size);
  int64_t *res = (int64_t *)malloc(sizeof(int64_t) * n);
  for (int i = 0; i < size; i++) {
    arr[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    arr[get<0>(vect[i])]++;
  }
  int64_t *st = constructST(arr, size);
  for (int i = 0; i < n; i++) {
    res[get<2>(vect[i])] =
        getSum(st, size, get<0>(vect[i]) + 1, get<1>(vect[i]));
    updateValue(arr, st, size, get<0>(vect[i]), 0);
  }
  for (int i = 0; i < n; i++) {
    cout << res[i] << endl;
  }
}

### Prompt

Develop a solution in CPP 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;
int64_t getMid(int64_t s, int64_t e) { return s + (e - s) / 2; }
bool compareTuple(tuple<int64_t, int64_t, int> a,
                  tuple<int64_t, int64_t, int> b) {
  return get<1>(a) > get<1>(b);
}
int64_t constructSTUtil(int64_t arr[], int64_t ss, int64_t se, int64_t *st,
                        int64_t si) {
  if (ss == se) {
    st[si] = arr[ss];
    return arr[ss];
  }
  int64_t mid = getMid(ss, se);
  st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) +
           constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);
  return st[si];
}
int64_t *constructST(int64_t arr[], int64_t n) {
  int64_t x = (int64_t)(ceil(log2(n)));
  int64_t max_size = 2 * (int64_t)pow(2, x) - 1;
  int64_t *st = new int64_t[max_size];
  constructSTUtil(arr, 0, n - 1, st, 0);
  return st;
}
int64_t getSumUtil(int64_t *st, int64_t ss, int64_t se, int64_t qs, int64_t qe,
                   int64_t si) {
  if (qs <= ss && qe >= se) return st[si];
  if (se < qs || ss > qe) return 0;
  int64_t mid = getMid(ss, se);
  return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) +
         getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);
}
int64_t getSum(int64_t *st, int64_t n, int64_t qs, int64_t qe) {
  if (qs < 0 || qe > n || qs > qe) {
    cout << "Invalid Input";
    return -1;
  }
  return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
void updateValueUtil(int64_t *st, int64_t ss, int64_t se, int64_t i,
                     int64_t diff, int64_t si) {
  if (i < ss || i > se) return;
  st[si] = st[si] + diff;
  if (se != ss) {
    int64_t mid = getMid(ss, se);
    updateValueUtil(st, ss, mid, i, diff, 2 * si + 1);
    updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2);
  }
}
void updateValue(int64_t arr[], int64_t *st, int64_t n, int64_t i,
                 int64_t new_val) {
  if (i < 0 || i > n - 1) {
    cout << "Invalid Input";
    return;
  }
  int64_t diff = new_val - arr[i];
  arr[i] = new_val;
  updateValueUtil(st, 0, n - 1, i, diff, 0);
}
int main() {
  int n = 0;
  cin >> n;
  vector<tuple<int64_t, int64_t, int>> vect;
  vector<int> values;
  int size = 2 * n;
  for (int i = 0; i < n; i++) {
    int64_t l, r = 0;
    cin >> l;
    cin >> r;
    values.push_back(l);
    values.push_back(r);
    tuple<int64_t, int64_t, int> tmp = make_tuple(l, r, i);
    vect.push_back(tmp);
  }
  std::sort(values.begin(), values.end());
  for (int i = 0; i < n; i++) {
    get<0>(vect[i]) =
        std::lower_bound(values.begin(), values.end(), get<0>(vect[i])) -
        values.begin();
    get<1>(vect[i]) =
        std::lower_bound(values.begin(), values.end(), get<1>(vect[i])) -
        values.begin();
  }
  std::sort(vect.begin(), vect.end(), compareTuple);
  int64_t *arr = (int64_t *)malloc(sizeof(int64_t) * size);
  int64_t *res = (int64_t *)malloc(sizeof(int64_t) * n);
  for (int i = 0; i < size; i++) {
    arr[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    arr[get<0>(vect[i])]++;
  }
  int64_t *st = constructST(arr, size);
  for (int i = 0; i < n; i++) {
    res[get<2>(vect[i])] =
        getSum(st, size, get<0>(vect[i]) + 1, get<1>(vect[i]));
    updateValue(arr, st, size, get<0>(vect[i]), 0);
  }
  for (int i = 0; i < n; i++) {
    cout << res[i] << endl;
  }
}

```