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
import java.util.*;
import java.io.*;

public class F {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        int[] c = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            String[] tokens = br.readLine().split(" ");
            a[i] = Integer.parseInt(tokens[0]);
            b[i] = Integer.parseInt(tokens[1]);
            c[i] = Integer.parseInt(tokens[2]);
        }
        Solution solution = new Solution(n, a, b, c);
        solution.solve();
        System.out.println(solution.getOutputString());
    }
}

class Solution {
    public Solution(int n, int[] a, int[] b, int[] c) {
        this.n = n;
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public void solve() {
        TreeMap<Integer, Integer> mpAB = new TreeMap<>();
        for(int i = 1; i <= n; i++) {
            mpAB.put(a[i], 0);
            mpAB.put(b[i], 0);
        }
        int tmp = 0;
        for(Map.Entry<Integer, Integer> entry : mpAB.entrySet()) {
            tmp++;
            entry.setValue(tmp);
        }
        for(int i = 1; i <= n; i++) {
            a[i] = mpAB.get(a[i]);
            b[i] = mpAB.get(b[i]);
        }
        ListInt[] lstB = new ListInt[mpAB.size() + 1];
        for(int i = 1; i <= mpAB.size(); i++) {
            lstB[i] = new ListInt();
        }
        for(int i = 1; i <= n; i++) {
            lstB[b[i]].add(i);
        }
        SegmentTree segTreeF = new SegmentTree(0, mpAB.size());
        SegmentTree segTreeG = new SegmentTree(0, mpAB.size());
        for(int i = 1; i <= mpAB.size(); i++) {
            for(int id : lstB[i]) {
                if(c[id] == 1) {
                    segTreeG.update(0, a[id] - 1, 1);
                }
                else {
                    segTreeF.update(0, a[id] - 1, 1);
                }
            }
            int f = segTreeG.query(0, i - 1);
            int g = segTreeF.query(0, i - 1);
            segTreeF.update(i, i, f);
            segTreeG.update(i, i, g);
        }
        ans = Math.max(segTreeF.query(0, mpAB.size()), segTreeG.query(0, mpAB.size()));
    }

    public String getOutputString() {
        return String.valueOf(ans);
    }

    private int n;
    private int[] a;
    private int[] b;
    private int[] c;
    private int ans;
}

class ListInt extends ArrayList<Integer> {}

class SegmentTree {
    public SegmentTree(int fst, int lst) {
        this.fst = fst;
        this.lst = lst;
        int sz = 1;
        while(sz <= lst - fst + 1) {
            sz *= 2;
        }
        sz *= 2;
        this.dt = new int[sz + 1];
        this.lz = new int[sz + 1];
    }

    public void update(int l, int h, int val) {
        recursiveUpdate(1, fst, lst, l, h, val);
    }

    public int query(int l, int h) {
        return recursiveQuery(1, fst, lst, l, h);
    }

    private void recursiveUpdate(int x, int low, int high, int l, int h, int val) {
        if(low > h || high < l) {
            return;
        }
        if(low >= l && high <= h) {
            dt[x] += val;
            lz[x] += val;
            return;
        }
        downLz(x);
        int mid = (low + high) / 2;
        recursiveUpdate(x * 2, low, mid, l, h, val);
        recursiveUpdate(x * 2 + 1, mid + 1, high, l, h, val);
        dt[x] = Math.max(dt[x * 2], dt[x * 2 + 1]);
    }

    private int recursiveQuery(int x, int low, int high, int l, int h) {
        if(low > h || high < l) {
            return 0;
        }
        if(low >= l && high <= h) {
            return dt[x];
        }
        downLz(x);
        int mid = (low + high) / 2;
        return Math.max(recursiveQuery(x * 2, low, mid, l, h), recursiveQuery(x * 2 + 1, mid + 1, high, l, h));
    }

    private void downLz(int x) {
        dt[x * 2] += lz[x];
        lz[x * 2] += lz[x];
        dt[x * 2 + 1] += lz[x];
        lz[x * 2 + 1] += lz[x];
        lz[x] = 0;
    }

    private int fst;
    private int lst;
    private int[] dt;
    private int[] lz;
}
