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

public class F {
    static final boolean RUN_TIMING = false;
    static char[] inputBuffer = new char[1 << 20];
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1 << 20);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        int n = ipar();
        PriorityQueue<int[]> front = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> back1 = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> back2 = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < n; i++) {
            int[] interval = {ipar(), ipar(), ipar()};
            front.add(interval);
        }
        front.add(new int[]{2000000000, 2000000000, 1});
        int match = 0;
        while (!front.isEmpty()) {
            int[] curr = front.remove();
            while (!back1.isEmpty() && back1.peek()[1] < curr[0]) {
                int[] end = back1.remove();
                if (!back2.isEmpty()) {
                    match++;
                    back2.remove();
                }
            }
            while (!back2.isEmpty() && back2.peek()[1] < curr[0]) {
                int[] end = back2.remove();
                if (!back1.isEmpty()) {
                    match++;
                    back1.remove();
                }
            }
            if (curr[2] == 1) {
                back1.add(curr);
            } else {
                back2.add(curr);
            }
            // out.print("Front:");
            // for (int[] a : front) {
            //     out.print(" ");
            //     out.print(Arrays.toString(a));
            // }
            // out.println();
            // out.print("Back 1:");
            // for (int[] a : back1) {
            //     out.print(" ");
            //     out.print(Arrays.toString(a));
            // }
            // out.println();
            // out.print("Back 2:");
            // for (int[] a : back2) {
            //     out.print(" ");
            //     out.print(Arrays.toString(a));
            // }
            // out.println();
            // out.println();
        }
        out.println(n - match);
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        int len = 0;
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            inputBuffer[len] = (char)c;
            len++;
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return new String(inputBuffer, 0, len);
    }

    public String linepar() throws IOException {
        int len = 0;
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            inputBuffer[len] = (char)c;
            len++;
        }
        return new String(inputBuffer, 0, len);
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new F().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time / 1000000.0);
        }
        out.flush();
        in.close();
    }
}
