#include <bits/stdc++.h>
using namespace std;
long long i, j, n, t, k, arr[2005001], seg[5000001], ans[2500001];
pair<long long, pair<long long, long>> a[2500001];
map<long long, long long> m;
void upd(long long h, long long l, long long r, long long val, long long ind) {
  if (ind < l || ind > r) return;
  if (ind == l && ind == r) {
    seg[h] = val;
    return;
  }
  upd(h * 2, l, (l + r) / 2, val, ind);
  upd(h * 2 + 1, (l + r) / 2 + 1, r, val, ind);
  seg[h] = seg[h * 2] + seg[h * 2 + 1];
}
long long get(long long h, long long l, long long r, long long L, long long R) {
  if (l > R || r < L) return 0;
  if (l >= L && r <= R) return seg[h];
  return get(h * 2, l, (l + r) / 2, L, R) +
         get(h * 2 + 1, (l + r) / 2 + 1, r, L, R);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  t = 1;
  for (i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second.first;
    arr[t] = a[i].first;
    m[arr[t]] = 0;
    t++;
    arr[t] = a[i].second.first;
    m[arr[t]] = 0;
    t++;
    a[i].second.second = i;
  }
  t--;
  sort(arr + 1, arr + 1 + t);
  for (i = 1; i <= t; i++) {
    if (m[arr[i]] == 0) m[arr[i]] = i;
  }
  for (i = 1; i <= n; i++) {
    a[i].first = m[a[i].first];
    a[i].second.first = m[a[i].second.first];
    upd(1, 1, t, 1, a[i].second.first);
  }
  sort(a + 1, a + 1 + n);
  for (i = 1; i <= n; i++) {
    for (j = i - 1; j >= 1; j--) {
      if (a[j].first == -1 || a[j].first == a[i].first)
        break;
      else if (a[j].first < a[i].first) {
        a[j].first = -1;
        upd(1, 1, t, 0, a[j].second.first);
      }
    }
    ans[a[i].second.second] = get(1, 1, t, a[i].first, a[i].second.first - 1);
  }
  for (i = 1; i <= n; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}

### Prompt

Generate a Cpp solution 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;
long long i, j, n, t, k, arr[2005001], seg[5000001], ans[2500001];
pair<long long, pair<long long, long>> a[2500001];
map<long long, long long> m;
void upd(long long h, long long l, long long r, long long val, long long ind) {
  if (ind < l || ind > r) return;
  if (ind == l && ind == r) {
    seg[h] = val;
    return;
  }
  upd(h * 2, l, (l + r) / 2, val, ind);
  upd(h * 2 + 1, (l + r) / 2 + 1, r, val, ind);
  seg[h] = seg[h * 2] + seg[h * 2 + 1];
}
long long get(long long h, long long l, long long r, long long L, long long R) {
  if (l > R || r < L) return 0;
  if (l >= L && r <= R) return seg[h];
  return get(h * 2, l, (l + r) / 2, L, R) +
         get(h * 2 + 1, (l + r) / 2 + 1, r, L, R);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  t = 1;
  for (i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second.first;
    arr[t] = a[i].first;
    m[arr[t]] = 0;
    t++;
    arr[t] = a[i].second.first;
    m[arr[t]] = 0;
    t++;
    a[i].second.second = i;
  }
  t--;
  sort(arr + 1, arr + 1 + t);
  for (i = 1; i <= t; i++) {
    if (m[arr[i]] == 0) m[arr[i]] = i;
  }
  for (i = 1; i <= n; i++) {
    a[i].first = m[a[i].first];
    a[i].second.first = m[a[i].second.first];
    upd(1, 1, t, 1, a[i].second.first);
  }
  sort(a + 1, a + 1 + n);
  for (i = 1; i <= n; i++) {
    for (j = i - 1; j >= 1; j--) {
      if (a[j].first == -1 || a[j].first == a[i].first)
        break;
      else if (a[j].first < a[i].first) {
        a[j].first = -1;
        upd(1, 1, t, 0, a[j].second.first);
      }
    }
    ans[a[i].second.second] = get(1, 1, t, a[i].first, a[i].second.first - 1);
  }
  for (i = 1; i <= n; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}

```