E. Mars
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the solar system, it is often said that the most habitable planet besides Earth is Mars. Indeed, scientists have recently begun settling on Mars and have set up a base for permanent living. However, while Mars has an abundance of water and soil nutrients, it's missing the greatest natural resource: Milk! Unfortunately, this means that the scientists must import milk from Earth in order to sustain themselves.

Johnny, one of the scientists, has a particular affinity for milk. He has knowledge of spaceship trips which can transport jugs of milk from Earth to Mars and vice versa. Each of these trips has a departure and arrival time, and all of these times are distinct from each other.

Due to restrictions regarding waste, in order to import milk, Johnny must place an empty jug of milk on a spaceship bound for Earth where it will be filled immediately. He can then request for a particular spaceship bound for Mars to carry the milk back, where Johnny can empty the milk jug in a large storage container. Each spaceship can only carry one of Johnny's milk jugs at most (other scientists want to use the spaceships as well!).

Before any of the spaceships begin transporting items, Johnny has two empty milk jugs on hand. Given this knowledge, Johnny would like to know the maximum jugs' worth of milk he can import from Earth with the spaceships available.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of spaceship trips.

The next $$$n$$$ lines each contain three integers describing a spaceship trip, with the $$$i$$$-th line containing $$$l_i$$$, $$$r_i$$$, and $$$t_i$$$ ($$$0 \le l_i \lt r_i \le 10^9$$$, $$$t_i \in \{0, 1\}$$$) — the departure time, the arrival time, and the trip type, respectively. If $$$t_i = 0$$$, the trip is bound for Earth, and if $$$t_i = 1$$$, the trip is bound for Mars.

Output

Output a single integer — the maximum jugs' worth of milk that Johnny can import from Earth.

Examples
Input
4
0 1 0
2 3 1
4 5 0
6 7 1
Output
2
Input
6
0 4 0
7 8 1
1 5 0
9 10 1
2 6 0
11 12 1
Output
2
Note

In the first test case, Johnny can place an empty milk jug on the spaceship departing at time $$$0$$$ for Earth, and schedule it to return on the spaceship departing at time $$$2$$$ for Mars. He can then empty that milk jug in storage, place it on the spaceship departing at time $$$4$$$ for Earth, and schedule it to return on the spaceship departing at time $$$6$$$ for Mars. The filled milk jug will then be emptied into Johnny's storage. In total, Johnny will have $$$2$$$ jugs' worth of milk in storage after all trips have occurred.

In the second test case, Johnny can schedule his trips as follows:

  • At time $$$0$$$, place an empty milk jug on the spaceship departing for Earth.
  • At time $$$1$$$, place the second empty milk jug on the spaceship departing for Earth.
  • Request a filled milk jug to return on the spaceship departing for Mars at time $$$7$$$.
  • Request another filled milk jug to return on the spaceship departing for Mars at time $$$9$$$.
In total, Johnny will have $$$2$$$ jugs' worth of milk in storage after all trips have occurred.