#include <bits/stdc++.h>
using Point = int;
using Segment = std::pair<Point, Point>;
template <class T>
auto Compact(const std::vector<T> &full) -> std::vector<int>;
struct SumTree {
  std::vector<int> sums;
  SumTree(size_t size) : sums(size + 1, 0) {}
  void add(size_t pos, int change);
  auto sum(size_t end) const -> int;
  auto sum(size_t begin, size_t end) const -> int;
};
auto main() -> int {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  size_t count;
  std::cin >> count;
  std::vector<Segment> segments(count);
  for (auto &[l, r] : segments) {
    std::cin >> l >> r;
  }
  std::vector<int> coords;
  for (auto [l, r] : segments) {
    coords.push_back(l);
    coords.push_back(r);
  }
  auto compact_coords = Compact(coords);
  for (size_t i = 0; i < count; ++i) {
    segments[i] = {compact_coords[2 * i], compact_coords[2 * i + 1]};
  }
  auto indices = Compact(segments);
  std::sort(segments.begin(), segments.end());
  auto fenwick = SumTree(2 * count);
  auto answers = std::vector<int>(count);
  for (auto it = segments.rbegin(); it != segments.rend(); ++it) {
    answers[std::distance(segments.begin(), it.base() - 1)] =
        fenwick.sum(it->first, it->second);
    fenwick.add(it->second, +1);
  }
  for (size_t i = 0; i < count; ++i) {
    std::cout << answers[indices[i]] << ' ';
  }
  return 0;
}
auto SumTree::sum(size_t end) const -> int {
  int result = 0;
  for (size_t i = end; i > 0; i &= i - 1) {
    result += sums[i];
  }
  return result;
}
void SumTree::add(size_t pos, int change) {
  for (size_t x = pos; x < sums.size(); x |= x + 1) {
    sums[x + 1] += change;
  }
}
auto SumTree::sum(size_t begin, size_t end) const -> int {
  return sum(end) - sum(begin);
}
template <class T>
auto Compact(const std::vector<T> &full) -> std::vector<int> {
  std::vector<int> indices(full.size());
  for (size_t i = 0; i < full.size(); ++i) {
    indices[i] = i;
  }
  std::sort(indices.begin(), indices.end(),
            [&full](int x, int y) { return full[x] < full[y]; });
  std::vector<int> inversed(full.size());
  for (int i = 0; i < full.size(); ++i) {
    inversed[indices[i]] = i;
  }
  return inversed;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 Point = int;
using Segment = std::pair<Point, Point>;
template <class T>
auto Compact(const std::vector<T> &full) -> std::vector<int>;
struct SumTree {
  std::vector<int> sums;
  SumTree(size_t size) : sums(size + 1, 0) {}
  void add(size_t pos, int change);
  auto sum(size_t end) const -> int;
  auto sum(size_t begin, size_t end) const -> int;
};
auto main() -> int {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  size_t count;
  std::cin >> count;
  std::vector<Segment> segments(count);
  for (auto &[l, r] : segments) {
    std::cin >> l >> r;
  }
  std::vector<int> coords;
  for (auto [l, r] : segments) {
    coords.push_back(l);
    coords.push_back(r);
  }
  auto compact_coords = Compact(coords);
  for (size_t i = 0; i < count; ++i) {
    segments[i] = {compact_coords[2 * i], compact_coords[2 * i + 1]};
  }
  auto indices = Compact(segments);
  std::sort(segments.begin(), segments.end());
  auto fenwick = SumTree(2 * count);
  auto answers = std::vector<int>(count);
  for (auto it = segments.rbegin(); it != segments.rend(); ++it) {
    answers[std::distance(segments.begin(), it.base() - 1)] =
        fenwick.sum(it->first, it->second);
    fenwick.add(it->second, +1);
  }
  for (size_t i = 0; i < count; ++i) {
    std::cout << answers[indices[i]] << ' ';
  }
  return 0;
}
auto SumTree::sum(size_t end) const -> int {
  int result = 0;
  for (size_t i = end; i > 0; i &= i - 1) {
    result += sums[i];
  }
  return result;
}
void SumTree::add(size_t pos, int change) {
  for (size_t x = pos; x < sums.size(); x |= x + 1) {
    sums[x + 1] += change;
  }
}
auto SumTree::sum(size_t begin, size_t end) const -> int {
  return sum(end) - sum(begin);
}
template <class T>
auto Compact(const std::vector<T> &full) -> std::vector<int> {
  std::vector<int> indices(full.size());
  for (size_t i = 0; i < full.size(); ++i) {
    indices[i] = i;
  }
  std::sort(indices.begin(), indices.end(),
            [&full](int x, int y) { return full[x] < full[y]; });
  std::vector<int> inversed(full.size());
  for (int i = 0; i < full.size(); ++i) {
    inversed[indices[i]] = i;
  }
  return inversed;
}

```