#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pqd = priority_queue<T>;
template <typename T>
using pqa = priority_queue<T, vector<T>, greater<T>>;
string to_string(string c) { return string(c); }
string to_string(char ch) { return string(1, ch); }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N>
string to_string(bitset<N> B) {
  string second = "";
  for (long long i = 0; i < (long long)N; i++) second += (char)'0' + B[i];
  return second;
}
template <typename T, typename U>
string to_string(pair<T, U> P) {
  return "{" + to_string(P.first) + "," + to_string(P.second) + "}";
}
template <typename T>
string to_string(T A) {
  string second = "[";
  bool first = 0;
  for (auto x : A) {
    if (first) second += " ";
    first = 1;
    second += to_string(x);
  }
  return second + "]";
}
template <typename T, size_t N>
string to_string(T (&A)[N]) {
  string second = "[";
  bool first = 0;
  for (long long i = 0; i < N; i++) {
    if (first) second += " ";
    first = 1;
    second += to_string(A[i]);
  }
  return second + "]";
}
void _deb() { cerr << "\n"; }
template <typename T, typename... U>
void _deb(const T &t, const U &...u) {
  cerr << to_string(t);
  if (sizeof...(u)) cout << ", ";
  _deb(u...);
}
long long ceil(long long a, long long b) {
  return a / b + (a % b && (a ^ b) > 0);
}
long long floor(long long a, long long b) {
  return a / b - (a % b && (a ^ b) < 0);
}
long long SBITS(long long n) { return __builtin_popcountll(n); }
long long BITS(long long n) { return 63 - __builtin_clzll(n); }
const long long MX = 5e5 + 5;
const long long OO = 1e18;
const long long MOD = 1e9 + 7;
long long DX[8] = {1, 0, -1, 0, 1, -1, 1, -1};
long long DY[8] = {0, 1, 0, -1, 1, -1, -1, 1};
struct NODE {
  long long val;
  NODE() { val = 0; }
  NODE(long long n) { val = n; }
  NODE merge(const NODE &l, const NODE &r) {
    this->val = l.val + r.val;
    return *this;
  }
  friend ostream &operator<<(ostream &cout, NODE n) { return cout << n.val; }
};
string to_string(NODE n) { return to_string(n.val); }
struct segtree {
  long long n;
  vector<NODE> t;
  segtree(long long _n) : n(_n) {
    assert(_n > 0);
    t.resize(4 * n);
  }
  segtree(const vector<long long> &a) : n((long long)a.size()) {
    assert(n > 0);
    t.resize(4 * n);
    for (long long i = 0; i < (long long)a.size(); i++) update(i, a[i]);
  }
  void update(long long node, long long l, long long r, long long pos,
              long long val) {
    if (l == r) {
      t[node] = val;
      return;
    }
    long long mid = (l + r) / 2;
    if (pos <= mid)
      update(2 * node, l, mid, pos, val);
    else
      update(2 * node + 1, mid + 1, r, pos, val);
    t[node].merge(t[2 * node], t[2 * node + 1]);
  }
  void update(long long pos, long long val) { update(1, 0, n - 1, pos, val); }
  NODE query(long long node, long long l, long long r, long long L,
             long long R) {
    if (R < l || L > r) return NODE();
    if (L <= l && R >= r) return t[node];
    long long mid = (l + r) / 2;
    return NODE().merge(query(2 * node, l, mid, L, R),
                        query(2 * node + 1, mid + 1, r, L, R));
  }
  NODE query(long long node, long long l, long long r, long long pos) {
    if (l == r) return t[node];
    long long mid = (l + r) / 2;
    if (pos <= mid)
      return query(node * 2, l, mid, pos);
    else
      return query(node * 2 + 1, mid + 1, r, pos);
  }
  NODE query(long long pos) { return query(1, 0, n - 1, pos); }
  NODE query(long long L, long long R) { return query(1, 0, n - 1, L, R); }
  long long lower_bound(long long node, long long l, long long r, long long x) {
    if (x >= t[node].val)
      return r;
    else if (l == r)
      return r;
    long long mid = (l + r) / 2;
    if (x <= t[2 * node].val)
      return lower_bound(2 * node, l, mid, x);
    else
      return lower_bound(2 * node + 1, mid + 1, r, x - t[2 * node].val);
  }
  long long lower_bound(long long x) { return lower_bound(1, 0, n - 1, x); };
  long long upper_bound(long long node, long long l, long long r, long long x) {
    if (x >= t[node].val)
      return r;
    else if (l == r)
      return r;
    long long mid = (l + r) / 2;
    if (x < t[2 * node].val)
      return upper_bound(2 * node, l, mid, x);
    else
      return upper_bound(2 * node + 1, mid + 1, r, x - t[2 * node].val);
  }
  long long upper_bound(long long x) { return upper_bound(1, 0, n - 1, x); }
};
void solve() {
  long long n;
  cin >> n;
  vector<long long> last(n, -1), ans(n), a(2 * n);
  segtree s(2 * n);
  vector<pair<long long, long long>> seg(2 * n);
  for (long long i = 0; i < 2 * n; i += 2)
    cin >> seg[i].first >> seg[i + 1].first,
        seg[i].second = seg[i + 1].second = i / 2;
  sort(seg.begin(), seg.end());
  long long ctr = 0;
  for (auto x : seg) a[ctr++] = x.second;
  for (__typeof(ctr) i = (0) - ((0) > (ctr)); i != (ctr) - ((0) > (ctr));
       i += 1 - 2 * ((0) > (ctr))) {
    if (last[a[i]] != -1) {
      ans[a[i]] = s.query(last[a[i]], i).val;
      s.update(last[a[i]], 1);
    }
    last[a[i]] = i;
  }
  for (auto x : ans) cout << x << "\n";
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) solve();
  cerr << "Time: " << (float)clock() / CLOCKS_PER_SEC << " s"
       << "\n";
  return 0;
}

### 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;
template <typename T>
using pqd = priority_queue<T>;
template <typename T>
using pqa = priority_queue<T, vector<T>, greater<T>>;
string to_string(string c) { return string(c); }
string to_string(char ch) { return string(1, ch); }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N>
string to_string(bitset<N> B) {
  string second = "";
  for (long long i = 0; i < (long long)N; i++) second += (char)'0' + B[i];
  return second;
}
template <typename T, typename U>
string to_string(pair<T, U> P) {
  return "{" + to_string(P.first) + "," + to_string(P.second) + "}";
}
template <typename T>
string to_string(T A) {
  string second = "[";
  bool first = 0;
  for (auto x : A) {
    if (first) second += " ";
    first = 1;
    second += to_string(x);
  }
  return second + "]";
}
template <typename T, size_t N>
string to_string(T (&A)[N]) {
  string second = "[";
  bool first = 0;
  for (long long i = 0; i < N; i++) {
    if (first) second += " ";
    first = 1;
    second += to_string(A[i]);
  }
  return second + "]";
}
void _deb() { cerr << "\n"; }
template <typename T, typename... U>
void _deb(const T &t, const U &...u) {
  cerr << to_string(t);
  if (sizeof...(u)) cout << ", ";
  _deb(u...);
}
long long ceil(long long a, long long b) {
  return a / b + (a % b && (a ^ b) > 0);
}
long long floor(long long a, long long b) {
  return a / b - (a % b && (a ^ b) < 0);
}
long long SBITS(long long n) { return __builtin_popcountll(n); }
long long BITS(long long n) { return 63 - __builtin_clzll(n); }
const long long MX = 5e5 + 5;
const long long OO = 1e18;
const long long MOD = 1e9 + 7;
long long DX[8] = {1, 0, -1, 0, 1, -1, 1, -1};
long long DY[8] = {0, 1, 0, -1, 1, -1, -1, 1};
struct NODE {
  long long val;
  NODE() { val = 0; }
  NODE(long long n) { val = n; }
  NODE merge(const NODE &l, const NODE &r) {
    this->val = l.val + r.val;
    return *this;
  }
  friend ostream &operator<<(ostream &cout, NODE n) { return cout << n.val; }
};
string to_string(NODE n) { return to_string(n.val); }
struct segtree {
  long long n;
  vector<NODE> t;
  segtree(long long _n) : n(_n) {
    assert(_n > 0);
    t.resize(4 * n);
  }
  segtree(const vector<long long> &a) : n((long long)a.size()) {
    assert(n > 0);
    t.resize(4 * n);
    for (long long i = 0; i < (long long)a.size(); i++) update(i, a[i]);
  }
  void update(long long node, long long l, long long r, long long pos,
              long long val) {
    if (l == r) {
      t[node] = val;
      return;
    }
    long long mid = (l + r) / 2;
    if (pos <= mid)
      update(2 * node, l, mid, pos, val);
    else
      update(2 * node + 1, mid + 1, r, pos, val);
    t[node].merge(t[2 * node], t[2 * node + 1]);
  }
  void update(long long pos, long long val) { update(1, 0, n - 1, pos, val); }
  NODE query(long long node, long long l, long long r, long long L,
             long long R) {
    if (R < l || L > r) return NODE();
    if (L <= l && R >= r) return t[node];
    long long mid = (l + r) / 2;
    return NODE().merge(query(2 * node, l, mid, L, R),
                        query(2 * node + 1, mid + 1, r, L, R));
  }
  NODE query(long long node, long long l, long long r, long long pos) {
    if (l == r) return t[node];
    long long mid = (l + r) / 2;
    if (pos <= mid)
      return query(node * 2, l, mid, pos);
    else
      return query(node * 2 + 1, mid + 1, r, pos);
  }
  NODE query(long long pos) { return query(1, 0, n - 1, pos); }
  NODE query(long long L, long long R) { return query(1, 0, n - 1, L, R); }
  long long lower_bound(long long node, long long l, long long r, long long x) {
    if (x >= t[node].val)
      return r;
    else if (l == r)
      return r;
    long long mid = (l + r) / 2;
    if (x <= t[2 * node].val)
      return lower_bound(2 * node, l, mid, x);
    else
      return lower_bound(2 * node + 1, mid + 1, r, x - t[2 * node].val);
  }
  long long lower_bound(long long x) { return lower_bound(1, 0, n - 1, x); };
  long long upper_bound(long long node, long long l, long long r, long long x) {
    if (x >= t[node].val)
      return r;
    else if (l == r)
      return r;
    long long mid = (l + r) / 2;
    if (x < t[2 * node].val)
      return upper_bound(2 * node, l, mid, x);
    else
      return upper_bound(2 * node + 1, mid + 1, r, x - t[2 * node].val);
  }
  long long upper_bound(long long x) { return upper_bound(1, 0, n - 1, x); }
};
void solve() {
  long long n;
  cin >> n;
  vector<long long> last(n, -1), ans(n), a(2 * n);
  segtree s(2 * n);
  vector<pair<long long, long long>> seg(2 * n);
  for (long long i = 0; i < 2 * n; i += 2)
    cin >> seg[i].first >> seg[i + 1].first,
        seg[i].second = seg[i + 1].second = i / 2;
  sort(seg.begin(), seg.end());
  long long ctr = 0;
  for (auto x : seg) a[ctr++] = x.second;
  for (__typeof(ctr) i = (0) - ((0) > (ctr)); i != (ctr) - ((0) > (ctr));
       i += 1 - 2 * ((0) > (ctr))) {
    if (last[a[i]] != -1) {
      ans[a[i]] = s.query(last[a[i]], i).val;
      s.update(last[a[i]], 1);
    }
    last[a[i]] = i;
  }
  for (auto x : ans) cout << x << "\n";
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) solve();
  cerr << "Time: " << (float)clock() / CLOCKS_PER_SEC << " s"
       << "\n";
  return 0;
}

```