#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
 public:
  SegmentTree(uint64_t _n) {
    size = pow(2, ceil(log2(_n))) * 2 - 1;
    seg_tree = new int64_t[size];
    for (int i = 0; i < size; ++i) seg_tree[i] = 0;
    n = _n;
  }
  ~SegmentTree() { delete[] seg_tree; }
  void increment(uint64_t pos) {
    pos += ((size + 1) / 2) - 1;
    while (1) {
      seg_tree[pos]++;
      if (pos == 0) {
        break;
      }
      pos = ((pos - 1) / 2);
    }
  }
  uint64_t count(uint64_t i) {
    return rec_count(0, i, 0, ((size + 1) / 2) - 1, 0);
  }
  void print() {
    for (int i = 0; i < size; ++i) cout << seg_tree[i] << " ";
    cout << endl;
  }

 private:
  uint64_t size;
  uint64_t n;
  int64_t* seg_tree;
  uint64_t rec_count(uint64_t qlow, uint64_t qhigh, uint64_t low, uint64_t high,
                     uint64_t pos) {
    if (qlow <= low && qhigh >= high) return seg_tree[pos];
    if (qlow > high || qhigh < low) return 0;
    uint64_t mid = (low + high) / 2;
    return rec_count(qlow, qhigh, low, mid, (2 * pos + 1)) +
           rec_count(qlow, qhigh, mid + 1, high, (2 * pos + 2));
  }
};
template <typename T>
vector<T> get_input_sequence(size_t n) {
  vector<T> sequence(n);
  for (size_t i = 0; i < n; ++i) cin >> sequence[i];
  return sequence;
}
struct Segment {
  int64_t id;
  int64_t i;
  int64_t j;
  int64_t includes;
};
int main() {
  std::ios_base::sync_with_stdio(false);
  int64_t n;
  cin >> n;
  vector<Segment> segments(n);
  for (int64_t id = 0; id < n; ++id) {
    segments[id].id = id;
    cin >> segments[id].i >> segments[id].j;
    segments[id].includes = 0;
  }
  sort(segments.begin(), segments.end(),
       [](Segment a, Segment b) { return a.j < b.j; });
  for (int i = 0; i < n; ++i) segments[i].j = i;
  sort(segments.begin(), segments.end(),
       [](Segment a, Segment b) { return a.i > b.i; });
  SegmentTree segment_tree(n);
  for (int64_t i = 0; i < n; ++i) {
    Segment* s = &segments[i];
    s->includes = segment_tree.count(s->j);
    segment_tree.increment(s->j);
  }
  sort(segments.begin(), segments.end(),
       [](Segment a, Segment b) { return a.id < b.id; });
  for (int64_t i = 0; i < n; ++i) cout << segments[i].includes << endl;
  return 0;
}

### Prompt

Your challenge is to write 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;
class SegmentTree {
 public:
  SegmentTree(uint64_t _n) {
    size = pow(2, ceil(log2(_n))) * 2 - 1;
    seg_tree = new int64_t[size];
    for (int i = 0; i < size; ++i) seg_tree[i] = 0;
    n = _n;
  }
  ~SegmentTree() { delete[] seg_tree; }
  void increment(uint64_t pos) {
    pos += ((size + 1) / 2) - 1;
    while (1) {
      seg_tree[pos]++;
      if (pos == 0) {
        break;
      }
      pos = ((pos - 1) / 2);
    }
  }
  uint64_t count(uint64_t i) {
    return rec_count(0, i, 0, ((size + 1) / 2) - 1, 0);
  }
  void print() {
    for (int i = 0; i < size; ++i) cout << seg_tree[i] << " ";
    cout << endl;
  }

 private:
  uint64_t size;
  uint64_t n;
  int64_t* seg_tree;
  uint64_t rec_count(uint64_t qlow, uint64_t qhigh, uint64_t low, uint64_t high,
                     uint64_t pos) {
    if (qlow <= low && qhigh >= high) return seg_tree[pos];
    if (qlow > high || qhigh < low) return 0;
    uint64_t mid = (low + high) / 2;
    return rec_count(qlow, qhigh, low, mid, (2 * pos + 1)) +
           rec_count(qlow, qhigh, mid + 1, high, (2 * pos + 2));
  }
};
template <typename T>
vector<T> get_input_sequence(size_t n) {
  vector<T> sequence(n);
  for (size_t i = 0; i < n; ++i) cin >> sequence[i];
  return sequence;
}
struct Segment {
  int64_t id;
  int64_t i;
  int64_t j;
  int64_t includes;
};
int main() {
  std::ios_base::sync_with_stdio(false);
  int64_t n;
  cin >> n;
  vector<Segment> segments(n);
  for (int64_t id = 0; id < n; ++id) {
    segments[id].id = id;
    cin >> segments[id].i >> segments[id].j;
    segments[id].includes = 0;
  }
  sort(segments.begin(), segments.end(),
       [](Segment a, Segment b) { return a.j < b.j; });
  for (int i = 0; i < n; ++i) segments[i].j = i;
  sort(segments.begin(), segments.end(),
       [](Segment a, Segment b) { return a.i > b.i; });
  SegmentTree segment_tree(n);
  for (int64_t i = 0; i < n; ++i) {
    Segment* s = &segments[i];
    s->includes = segment_tree.count(s->j);
    segment_tree.increment(s->j);
  }
  sort(segments.begin(), segments.end(),
       [](Segment a, Segment b) { return a.id < b.id; });
  for (int64_t i = 0; i < n; ++i) cout << segments[i].includes << endl;
  return 0;
}

```