#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  long long ans = 1;
  while (b) {
    if (b % 2) ans = ans * a % MOD;
    a = a * a % MOD;
    b /= 2;
  }
  return ans;
}
const int N = 5e5 + 3;
const long long mod = 1e9 + 7;
int n;
struct uzi {
  int l, r, i;
  bool operator<(const uzi &t) const { return l > t.l; }
} p[N];
int t[N], cnt;
void add(int p) {
  for (; p <= cnt; p += p & -p) t[p]++;
}
int get(int p) {
  int ans = 0;
  for (; p; p -= p & -p) ans += t[p];
  return ans;
}
int a[N << 1], ans[N];
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].l >> p[i].r;
    p[i].i = i;
    a[++cnt] = p[i].l;
    a[++cnt] = p[i].r;
  }
  sort(a + 1, a + 1 + cnt);
  cnt = unique(a + 1, a + 1 + cnt) - a - 1;
  for (int i = 1; i <= n; i++)
    p[i].l = lower_bound(a + 1, a + 1 + cnt, p[i].l) - a;
  for (int i = 1; i <= n; i++)
    p[i].r = lower_bound(a + 1, a + 1 + cnt, p[i].r) - a;
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; i++) {
    ans[p[i].i] = get(p[i].r);
    add(p[i].r);
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
  return 0;
}

### Prompt

Your task is to create 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 gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  long long ans = 1;
  while (b) {
    if (b % 2) ans = ans * a % MOD;
    a = a * a % MOD;
    b /= 2;
  }
  return ans;
}
const int N = 5e5 + 3;
const long long mod = 1e9 + 7;
int n;
struct uzi {
  int l, r, i;
  bool operator<(const uzi &t) const { return l > t.l; }
} p[N];
int t[N], cnt;
void add(int p) {
  for (; p <= cnt; p += p & -p) t[p]++;
}
int get(int p) {
  int ans = 0;
  for (; p; p -= p & -p) ans += t[p];
  return ans;
}
int a[N << 1], ans[N];
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].l >> p[i].r;
    p[i].i = i;
    a[++cnt] = p[i].l;
    a[++cnt] = p[i].r;
  }
  sort(a + 1, a + 1 + cnt);
  cnt = unique(a + 1, a + 1 + cnt) - a - 1;
  for (int i = 1; i <= n; i++)
    p[i].l = lower_bound(a + 1, a + 1 + cnt, p[i].l) - a;
  for (int i = 1; i <= n; i++)
    p[i].r = lower_bound(a + 1, a + 1 + cnt, p[i].r) - a;
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; i++) {
    ans[p[i].i] = get(p[i].r);
    add(p[i].r);
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
  return 0;
}

```