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.*;
 
public class Main extends PrintWriter {
    
    
    private void solve() {
        int n = sc.nextInt();
        int[][] intervals = new int[n][];
        int[][] events = new int[2*n][];
        for(int i = 0; i < n; i++) {
            intervals[i] = new int[] {sc.nextInt(), sc.nextInt(), sc.nextInt()-1};
            events[2*i] = new int[] {intervals[i][0], 1, intervals[i][2]};
            events[2*i+1] = new int[] {intervals[i][1], -1, intervals[i][2]};
        }
        Arrays.sort(events, Comparator.comparing((int[] arr) -> arr[0]));
        
        int[] x = new int[2*n];
        int x_ = 0;
        m = 0;
        for(int i = 0; i < 2*n; i++) {
            if(events[i][0] > x_) {
                x_ = events[i][0];
                x[m++] = x_;
            }
        }
                
        Arrays.sort(intervals, Comparator.comparing((int[] arr) -> arr[0]));
        
        max = new int[2][4*(m+1)];
        old = new boolean[2][4*(m+1)];
        lazy = new int[2][4*(m+1)];
        
        for(int i = m-1, j = n-1; i >= 0; i--) {
            
            
            for(int t = 0; t < 2; t++) {
                int best = range_query(1-t, 0, m, 1, i+1, m);
                range_add(t, 0, m, 1, i, i, best);
            }
            

            while(j >= 0 && intervals[j][0] == x[i]) {
                int t = intervals[j][2];
                int idx_r = find_idx(x, intervals[j][1]);
                range_add(t, 0, m, 1, idx_r, m, 1);
                j--;
            }
        }
        
        long ans = 0L;
        for(int t = 0; t < 2; t++) {
            ans = Math.max(ans, range_query(t, 0, m, 1, 0, m));
        }
        println(ans);
    }
    
    
    int find_idx(int[] x, int x_) {
        int l = -1;
        int r = m;
        while(l < r-1) {
            int mid = (l+r)/2;
            if(x[mid] <= x_) l = mid;
            else r = mid;
        }
        return l;
    }
    
    int m;
    int[][] max;
    boolean[][] old;
    int[][] lazy;
    
    void push(int t, int i, int x) {
        old[t][i] = true;
        lazy[t][i] += x;
    }
    
    void lazy_propagate(int t, int il, int ir, int i) {
        if(old[t][i]) {
            max[t][i] += lazy[t][i];
            if(il != ir) {
                push(t, 2*i, lazy[t][i]);
                push(t, 2*i+1, lazy[t][i]);
            }
            lazy_reset(t, i);
        }
    }
    
    void lazy_reset(int t, int i) {
        old[t][i] = false;
        lazy[t][i] = 0;
    }
    
    
    void range_add(int t, int il, int ir, int i, int ql, int qr, int x) {
        lazy_propagate(t, il, ir, i);
        if(ir < ql || il > qr) return;
        
        
        if(ql <= il && ir <= qr) {
            push(t, i, x);
            lazy_propagate(t, il, ir, i);
            return;
        }
        
        int imid = (il+ir)/2;
        range_add(t, il, imid, 2*i, ql, qr, x);
        range_add(t, imid+1, ir, 2*i+1, ql, qr, x);
        max[t][i] = Math.max(max[t][2*i], max[t][2*i+1]);
    }
    
    int range_query(int t, int il, int ir, int i, int ql, int qr) {
        lazy_propagate(t, il, ir, i);
        if(ir < ql || il > qr) return 0;
        
        if(ql <= il && ir <= qr) {
            return max[t][i];
        }
        
        int imid = (il+ir)/2;
        int max_l = range_query(t, il, imid, 2*i, ql, qr);
        int max_r = range_query(t, imid+1, ir, 2*i+1, ql, qr);
        return Math.max(max_l, max_r);
    }

//  Solution() throws FileNotFoundException { super(new File("output.txt")); }
//  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
    
  Main() { super(System.out); }
  InputReader sc = new InputReader(System.in);
  static class InputReader {
      InputReader(InputStream in) { this.in = in; } InputStream in;
      
      private byte[] buf = new byte[16384];
      private int    curChar;
      private int    numChars;
      
 
      public int read() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = in.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextLine() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isEndOfLine(c));
          return res.toString();
      }
 
      public String nextString() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isSpaceChar(c));
          return res.toString();
      }
 
      public long nextLong() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          long res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public int nextInt() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      private boolean isSpaceChar(int c) {
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      private boolean isEndOfLine(int c) {
          return c == '\n' || c == '\r' || c == -1;
      }
  }
 
    public static void main(String[] $) {
        new Thread(null, new Runnable() {
            public void run() {
                long start = System.nanoTime();
                try {Main solution = new Main(); solution.solve(); solution.close();} 
                catch (Exception e) {e.printStackTrace(); System.exit(1);}
                System.err.println((System.nanoTime()-start)/1E9);
            }
        }, "1", 1 << 27).start();
 
    }
    

}