#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
int n;
map<int, int> M;
class segment {
 public:
  int l, r, id;
  void input(int id) {
    read(l);
    read(r);
    M[l] = M[r] = 0;
    this->id = id;
  }
  void fix() {
    l = M[l];
    r = M[r];
  }
} s[200001];
int ft[400001];
void update(int u) {
  for (; u <= M.size(); u += u & -u) ft[u]++;
}
int get(int u) {
  int res = 0;
  for (; u > 0; u -= u & -u) res += ft[u];
  return res;
}
int ans[200001];
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) s[i].input(i);
  int cnt = 0;
  for (auto &t : M) t.second = ++cnt;
  for (int i = (1); i <= (n); i++) s[i].fix();
  sort(s + 1, s + n + 1, [](segment A, segment B) { return A.l > B.l; });
  for (int i = (1); i <= (n); i++) {
    ans[s[i].id] = get(s[i].r);
    update(s[i].r);
  }
  for (int i = (1); i <= (n); i++) writeln(ans[i]);
}

### 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;
using ll = long long;
using ld = long double;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
int n;
map<int, int> M;
class segment {
 public:
  int l, r, id;
  void input(int id) {
    read(l);
    read(r);
    M[l] = M[r] = 0;
    this->id = id;
  }
  void fix() {
    l = M[l];
    r = M[r];
  }
} s[200001];
int ft[400001];
void update(int u) {
  for (; u <= M.size(); u += u & -u) ft[u]++;
}
int get(int u) {
  int res = 0;
  for (; u > 0; u -= u & -u) res += ft[u];
  return res;
}
int ans[200001];
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) s[i].input(i);
  int cnt = 0;
  for (auto &t : M) t.second = ++cnt;
  for (int i = (1); i <= (n); i++) s[i].fix();
  sort(s + 1, s + n + 1, [](segment A, segment B) { return A.l > B.l; });
  for (int i = (1); i <= (n); i++) {
    ans[s[i].id] = get(s[i].r);
    update(s[i].r);
  }
  for (int i = (1); i <= (n); i++) writeln(ans[i]);
}

```