#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long n;
  cin >> n;
  vector<pair<long, pair<long, long> > > a;
  vector<long> t(n), r(n);
  for (long i = 0, l; i < n; i++) {
    cin >> l >> r[i] >> t[i];
    --t[i];
    a.push_back({l, {0, i}});
    a.push_back({r[i], {1, i}});
  }
  sort(a.begin(), a.end());
  set<pair<long, long> > s[2];
  long ans = n;
  for (auto it : a) {
    long cur = it.second.second;
    if (it.second.first) {
      long tmp = t[cur] ^ 1;
      if (s[t[cur]].count({r[cur], cur}) && !s[tmp].empty()) {
        ans--;
        s[tmp].erase(s[tmp].begin());
      }
      if (s[t[cur]].count({r[cur], cur})) s[t[cur]].erase({r[cur], cur});
    } else
      s[t[cur]].insert({r[cur], cur});
  }
  cout << ans;
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

You are given n segments [l_1, r_1], [l_2, r_2], ..., [l_n, r_n]. Each segment has one of two colors: the i-th segment's color is t_i.

Let's call a pair of segments i and j bad if the following two conditions are met:

  * t_i ≠ t_j; 
  * the segments [l_i, r_i] and [l_j, r_j] intersect, embed or touch, i. e. there exists an integer x such that x ∈ [l_i, r_i] and x ∈ [l_j, r_j]. 



Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — number of segments.

The next n lines contains three integers l_i, r_i, t_i (1 ≤ l_i ≤ r_i ≤ 10^9; t_i ∈ \{1, 2\}) — description of the i-th segment.

Output

Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.

Examples

Input


3
1 3 1
4 6 2
2 5 1


Output


2


Input


5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2


Output


4


Input


7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1


Output


5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long n;
  cin >> n;
  vector<pair<long, pair<long, long> > > a;
  vector<long> t(n), r(n);
  for (long i = 0, l; i < n; i++) {
    cin >> l >> r[i] >> t[i];
    --t[i];
    a.push_back({l, {0, i}});
    a.push_back({r[i], {1, i}});
  }
  sort(a.begin(), a.end());
  set<pair<long, long> > s[2];
  long ans = n;
  for (auto it : a) {
    long cur = it.second.second;
    if (it.second.first) {
      long tmp = t[cur] ^ 1;
      if (s[t[cur]].count({r[cur], cur}) && !s[tmp].empty()) {
        ans--;
        s[tmp].erase(s[tmp].begin());
      }
      if (s[t[cur]].count({r[cur], cur})) s[t[cur]].erase({r[cur], cur});
    } else
      s[t[cur]].insert({r[cur], cur});
  }
  cout << ans;
  return 0;
}

```