Rabbit Hooks

Interview

Time limit1sMemory limit1024 MB

Summary

Given N points recorded in order, find the most hops in a consecutive run where northeast and southeast hops strictly alternate.

Level: Easy3 of 10
Topics: Array, Dynamic programming
Solved: No attempts yet

Problem

Jänku-Juss is learning to make rabbit hooks (haak). His mother gave him a jumping exercise: jump over the haaks. She has other things to do, so she set his phone to record his jumps for later analysis. Each time Juss touches the ground, the phone records his X and Y coordinates. A hop is a move from one recorded point to the next. A west-to-east haak series is a sequence of consecutive hops with at least two hops, where the hops alternate between northeast and southeast. The first hop may go in either direction, but after that the directions must alternate. A northeast hop is one where both the X and Y coordinates increase. A southeast hop is one where the X coordinate increases and the Y coordinate decreases. Write a program that takes the recorded points and finds the longest west-to-east haak series.

Input

The first line contains the number of points recorded by the phone, $N$ ( $1 \le N \le 50\,000$ ). Each of the next $N$ lines contains two integers separated by a space, the coordinates $X_i$ and $Y_i$ of one point. The absolute values of the coordinates do not exceed 1,000,000.

Output

Print on a single line the number of hops in the longest west-to-east haak series. If Juss made no haak, print EI OLE.

Examples2

Example 1
Input
```
5
1 1
4 2
5 3
8 2
9 1
```
Expected output
```
2
```
Example 2
Input
```
4
2 1
6 2
4 1
8 2
```
Expected output
```
EI OLE
```