FJ ha implantado un nuevo chip RFID legible por máquina en cada una de sus vacas para poder monitorearlas y asegurarse de que todas regresen a casa después de un duro día de alimentación en los pastos.

Una noche, le intrigó observar que las vacas solían alinearse con muchos de sus números de serie en una progresión aritmética. Una vez, vio pasar cinco vacas con estos números de serie:

1 4 3 5 7

Una rápida inspección muestra que las vacas numeradas ~1, 3, 5~ y ~7~ estaban en el orden de una progresión aritmética (cada miembro de la progresión difiere del miembro de la progresión anterior en el mismo número entero).

Ayuda a FJ a descubrir si esto es una coincidencia. Dada una lista de ~N~ ~(1 \leq N \leq 2000)~ números de serie (enteros no negativos menores de mil millones), encuentre la subsecuencia más larga de esta lista que forme una progresión aritmética (las progresiones pueden ir de mayor a menor o de menor a mayor) e indique su longitud.

Entrada

• Línea 1: Una sola línea con el entero ~N~
• Líneas 2...N+1: ~N~ líneas, cada una con un solo entero. La primera línea representa el número de serie de la primera vaca, etc.

Salida

Un solo entero que corresponde a la longitud de la progresión más larga.

Ejemplo de Entrada

5
1
4
3
5
7

Ejemplo de Salida

4