#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct SegmentTree {
 private:
  int n;
  vector<T> tree;
  function<T(const T&, const T&)> op;
  T id;

 public:
  SegmentTree(function<T(const T&, const T&)> binaryOperation,
              const T identityValue)
      : op(binaryOperation), id(identityValue) {}
  void buildConstant(const int size, const T& val) {
    n = size;
    tree.resize(2 * n, id);
    for (int i = 0; i < n; ++i) {
      tree[n + i] = val;
    }
    for (int i = n - 1; i > 0; --i) {
      tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
    }
  }
  void build(const vector<T>& v) {
    n = v.size();
    tree.resize(2 * n, id);
    for (int i = 0; i < n; ++i) {
      tree[n + i] = v[i];
    }
    for (int i = n - 1; i > 0; --i) {
      tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
    }
  }
  void update(int pos, T delta) {
    tree[n + pos] += delta;
    for (int i = pos + n; i > 1; i >>= 1) {
      tree[i >> 1] = op(tree[i], tree[i ^ 1]);
    }
  }
  T query(int l, int r) {
    T result = id;
    l += n;
    r += n;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) result = op(result, tree[l++]);
      if (r & 1) result = op(result, tree[--r]);
    }
    return result;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  vector<tuple<int, int, int> > v(N);
  vector<int> results(N);
  for (int n = 0; n < N; ++n) {
    int left;
    int right;
    cin >> left;
    cin >> right;
    v[n] = make_tuple(left, right, n);
  }
  sort(v.begin(), v.end(),
       [](const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs) {
         return get<1>(lhs) < get<1>(rhs);
       });
  for (int n = 0; n < N; ++n) {
    get<1>(v[n]) = n;
  }
  sort(v.begin(), v.end(),
       [](const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs) {
         return get<0>(lhs) > get<0>(rhs);
       });
  auto sumOp = [](const int& lhs, const int& rhs) { return lhs + rhs; };
  SegmentTree<int> st(sumOp, 0);
  st.buildConstant(N, 0);
  for (int n = 0; n < N; ++n) {
    const int id = get<1>(v[n]);
    const int rank = get<2>(v[n]);
    results[rank] = st.query(0, id);
    st.update(id, 1);
  }
  for (int n = 0; n < N; ++n) {
    cout << results[n] << endl;
  }
  cout << endl;
  results.clear();
  v.clear();
  return 0;
}

### Prompt

Create a solution in CPP for 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>
struct SegmentTree {
 private:
  int n;
  vector<T> tree;
  function<T(const T&, const T&)> op;
  T id;

 public:
  SegmentTree(function<T(const T&, const T&)> binaryOperation,
              const T identityValue)
      : op(binaryOperation), id(identityValue) {}
  void buildConstant(const int size, const T& val) {
    n = size;
    tree.resize(2 * n, id);
    for (int i = 0; i < n; ++i) {
      tree[n + i] = val;
    }
    for (int i = n - 1; i > 0; --i) {
      tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
    }
  }
  void build(const vector<T>& v) {
    n = v.size();
    tree.resize(2 * n, id);
    for (int i = 0; i < n; ++i) {
      tree[n + i] = v[i];
    }
    for (int i = n - 1; i > 0; --i) {
      tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
    }
  }
  void update(int pos, T delta) {
    tree[n + pos] += delta;
    for (int i = pos + n; i > 1; i >>= 1) {
      tree[i >> 1] = op(tree[i], tree[i ^ 1]);
    }
  }
  T query(int l, int r) {
    T result = id;
    l += n;
    r += n;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) result = op(result, tree[l++]);
      if (r & 1) result = op(result, tree[--r]);
    }
    return result;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  vector<tuple<int, int, int> > v(N);
  vector<int> results(N);
  for (int n = 0; n < N; ++n) {
    int left;
    int right;
    cin >> left;
    cin >> right;
    v[n] = make_tuple(left, right, n);
  }
  sort(v.begin(), v.end(),
       [](const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs) {
         return get<1>(lhs) < get<1>(rhs);
       });
  for (int n = 0; n < N; ++n) {
    get<1>(v[n]) = n;
  }
  sort(v.begin(), v.end(),
       [](const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs) {
         return get<0>(lhs) > get<0>(rhs);
       });
  auto sumOp = [](const int& lhs, const int& rhs) { return lhs + rhs; };
  SegmentTree<int> st(sumOp, 0);
  st.buildConstant(N, 0);
  for (int n = 0; n < N; ++n) {
    const int id = get<1>(v[n]);
    const int rank = get<2>(v[n]);
    results[rank] = st.query(0, id);
    st.update(id, 1);
  }
  for (int n = 0; n < N; ++n) {
    cout << results[n] << endl;
  }
  cout << endl;
  results.clear();
  v.clear();
  return 0;
}

```