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
/**
 * author: derrick20
 * created: 8/29/20 9:20 PM
 */
import java.io.*;
import java.util.*;

public class BicoloredSegments implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new BicoloredSegments(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int[][] data = new int[3][N];
        TreeSet<Integer> distinct = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            data[0][i] = sc.nextInt();
            data[1][i] = sc.nextInt();
            data[2][i] = sc.nextInt() - 1;
            distinct.add(data[0][i]);
            distinct.add(data[1][i]);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int v : distinct) {
            map.put(v, map.size() + 1);
        }
        ArrayList<Integer>[] segs = new ArrayList[map.size() + 1];
        Arrays.setAll(segs, i -> new ArrayList<>());
        for (int i = 0; i < N; i++) {
            data[0][i] = map.get(data[0][i]);
            data[1][i] = map.get(data[1][i]);
            segs[data[1][i]].add(i);
        }
        SegmentTree[] dp = new SegmentTree[2];
        Arrays.setAll(dp, i -> new SegmentTree(map.size() + 1));
        for (int r = 1; r <= map.size(); r++) {
//            System.out.println("At r = " + r);
            for (int id : segs[r]) {
                int l = data[0][id];
                int type = data[2][id];
//                System.out.println("adding to " + 0 + " " + (l - 1) + " t = " + (1 - type));
                dp[1 - type].update(0, l - 1, 1);
//                System.out.println(dp[0] + "\n" + dp[1]);
            }
            int[] best = new int[]{0, 0};
            for (int id : segs[r]) {
                int l = data[0][id];
                int type = data[2][id];
//                dp[type].update(r, dp[type].query(0, r) + 1);
                // ahh
                best[type] = Math.max(best[type], dp[1 - type].query(0, l - 1));
            }
            dp[0].update(r, r, best[0]);
            dp[1].update(r, r, best[1]);
//            System.out.println(Arrays.toString(best));
        }
        out.println(Math.max(dp[0].query(1, map.size()), dp[1].query(1, map.size())));
        out.close();
    }

    static class SegmentTree {
        int[] max;
        int[] delta;
        int N;
        public SegmentTree(int size) {
            N = size;
            max = new int[4 * N];
            delta = new int[4 * N];
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                sb.append(query(i, i)).append(" ");
            }
            return sb.toString();
        }

        public void pushDown(int node) {
            delta[2 * node] += delta[node]; //AHH
            delta[2 * node + 1] += delta[node];
            delta[node] = 0;
        }

        public int eval(int node) {
            return max[node] + delta[node];
        }

        public void pullUp(int node) {
            max[node] = Math.max(eval(2 * node), eval(2 * node + 1));
        }

        public void update(int l, int r, int val) {
            update(1, 0, N - 1, l, r, val);
        }

        public void update(int node, int sl, int sr, int l, int r, int val) {
            if (l <= sl && sr <= r) {
                delta[node] += val;
            } else if (sr < l || r < sl) {
                return;
            } else {
                int mid = (sl + sr) / 2;
                pushDown(node);
                update(2 * node, sl, mid, l, r, val);
                update(2 * node + 1, mid + 1, sr, l, r, val);
                pullUp(node);
            }
        }

        public int query(int l, int r) {
            return query(1, 0, N - 1, l, r);
        }

        public int query(int node, int sl, int sr, int l, int r) {
            if (l <= sl && sr <= r) {
                return eval(node);
            } else if (sr < l || r < sl) {
                return 0;
            } else {
                int mid = (sl + sr) / 2;
                pushDown(node);
                int ans = Math.max(query(2 * node, sl, mid, l, r), query(2 * node + 1, mid + 1, sr, l, r));
                pullUp(node);
                return ans;
            }
        }
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}