#include <bits/stdc++.h>
using namespace std;
template <typename T>
T next_int() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') {
    p = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * p;
}
const int max_n = (int)3e5 + 227 + 1;
const int max_int = (int)1e9 + 227 + 1;
const int mod = (int)1e9 + 7;
vector<int> t[max_n * 4];
void merge_vector(vector<int> &a, vector<int> &b, vector<int> &c) {
  a.clear();
  int i = 0;
  int j = 0;
  while (i < b.size() || j < c.size()) {
    if (i == b.size()) {
      a.push_back(c[j]);
      j++;
    } else if (j == c.size()) {
      a.push_back(b[i]);
      i++;
    } else if (b[i] > c[j]) {
      a.push_back(c[j]);
      j++;
    } else {
      a.push_back(b[i]);
      i++;
    }
  }
}
int get(int v, int l, int r, int _l, int _r, int R) {
  if (_l > _r) return 0;
  if (l == _l && r == _r) {
    int ans = lower_bound(t[v].begin(), t[v].end(), R + 1) - t[v].begin();
    return ans;
  }
  int mid = (l + r) / 2;
  return get(v * 2, l, mid, _l, min(mid, _r), R) +
         get(v * 2 + 1, mid + 1, r, max(mid + 1, _l), _r, R);
}
vector<vector<int> > e;
void build(int v, int l, int r) {
  if (l == r) {
    t[v] = e[l];
    return;
  }
  int mid = (l + r) / 2;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
  merge_vector(t[v], t[v * 2], t[v * 2 + 1]);
}
int main() {
  int n = next_int<int>();
  vector<int> l(n), r(n);
  vector<pair<int, pair<int, int> > > xex;
  for (int i = 0; i < n; i++) {
    l[i] = next_int<int>();
    r[i] = next_int<int>();
    xex.push_back(make_pair(l[i], make_pair(0, i)));
    xex.push_back(make_pair(r[i], make_pair(1, i)));
  }
  sort(xex.begin(), xex.end());
  int k = 0;
  for (int i = 0; i < xex.size(); i++) {
    if (!i || xex[i].first != xex[i - 1].first) {
      k++;
    }
    if (xex[i].second.first == 0) {
      l[xex[i].second.second] = k;
    } else {
      r[xex[i].second.second] = k;
    }
  }
  e.resize(k + 1);
  for (int i = 0; i < n; i++) {
    e[l[i]].push_back(r[i]);
  }
  build(1, 1, k);
  for (int i = 0; i < n; i++) {
    cout << get(1, 1, k, l[i], r[i], r[i]) - 1 << "\n";
  }
}

### Prompt

Please create a solution in CPP 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;
template <typename T>
T next_int() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') {
    p = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * p;
}
const int max_n = (int)3e5 + 227 + 1;
const int max_int = (int)1e9 + 227 + 1;
const int mod = (int)1e9 + 7;
vector<int> t[max_n * 4];
void merge_vector(vector<int> &a, vector<int> &b, vector<int> &c) {
  a.clear();
  int i = 0;
  int j = 0;
  while (i < b.size() || j < c.size()) {
    if (i == b.size()) {
      a.push_back(c[j]);
      j++;
    } else if (j == c.size()) {
      a.push_back(b[i]);
      i++;
    } else if (b[i] > c[j]) {
      a.push_back(c[j]);
      j++;
    } else {
      a.push_back(b[i]);
      i++;
    }
  }
}
int get(int v, int l, int r, int _l, int _r, int R) {
  if (_l > _r) return 0;
  if (l == _l && r == _r) {
    int ans = lower_bound(t[v].begin(), t[v].end(), R + 1) - t[v].begin();
    return ans;
  }
  int mid = (l + r) / 2;
  return get(v * 2, l, mid, _l, min(mid, _r), R) +
         get(v * 2 + 1, mid + 1, r, max(mid + 1, _l), _r, R);
}
vector<vector<int> > e;
void build(int v, int l, int r) {
  if (l == r) {
    t[v] = e[l];
    return;
  }
  int mid = (l + r) / 2;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
  merge_vector(t[v], t[v * 2], t[v * 2 + 1]);
}
int main() {
  int n = next_int<int>();
  vector<int> l(n), r(n);
  vector<pair<int, pair<int, int> > > xex;
  for (int i = 0; i < n; i++) {
    l[i] = next_int<int>();
    r[i] = next_int<int>();
    xex.push_back(make_pair(l[i], make_pair(0, i)));
    xex.push_back(make_pair(r[i], make_pair(1, i)));
  }
  sort(xex.begin(), xex.end());
  int k = 0;
  for (int i = 0; i < xex.size(); i++) {
    if (!i || xex[i].first != xex[i - 1].first) {
      k++;
    }
    if (xex[i].second.first == 0) {
      l[xex[i].second.second] = k;
    } else {
      r[xex[i].second.second] = k;
    }
  }
  e.resize(k + 1);
  for (int i = 0; i < n; i++) {
    e[l[i]].push_back(r[i]);
  }
  build(1, 1, k);
  for (int i = 0; i < n; i++) {
    cout << get(1, 1, k, l[i], r[i], r[i]) - 1 << "\n";
  }
}

```