Arrow

Statement:

Bruce is playing the game Green Arrow. In the game, the ground is the x-axis and the targets are a number of vertical line segments in the first quadrant. There is no intersection between any two targets. Moreover, no target touches the x-axis. Bruce can control a game character, always located at (0,0), to shoot an arrow towards the first quadrant with an angle θ (0<θ<90) .There is no air resistance in the game. Thus, the trajectory of the arrow will be a standard parabola. The targets which are crossed by the trajectory are hit in the game, including those with only endpoints crossed by the trajectory.

In challenge mode, there are a number of rounds. In the first round, there is only one target. If Bruce hits the target, he can pass to the second round. In the second round, the target in the first round will appear and a new target will be added. Bruce has to hit both of the targets, so that he can pass to the next round. Similarly, in the k-th round, the targets in the previous k−1 rounds will appear and a new target is added. Bruce can pass to the next round only if he can make a shot to hit all targets in this round. Bruce has hacked the game and gets the locations of all targets. He wants to know the maximum number of rounds he can successfully pass. It is possible that Bruce can win the game, in which case there are no more rounds to pass after that.

Input:

The first line of input will consist of one integer, N (1 ≤ N ≤ 100 000), the number of rounds in the game. Each of the following Nlines will consist of three integers, xi (0 < xi < 109), yi1 and yi2 (0 < yi1 < yi2 < 109), which are the target i's horizontal position, the low endpoint, and the high endpoint, respectively.

Output:

Output one integer, the maximum number of rounds Bruce can pass.

Example Input:
5
2 8 12
5 4 5
3 8 10
6 2 3
1 3 7
	
Example Output:
3
	
Explanation:

The sample case is as shown in the following figure.

Time and memory limit:

  • 4s
  • 256MB

Problem source: DMOJ