Matcom Online Grader
III Copa UHEnded |
Hay un evento que tendrá lugar en la próxima semana y que ha de durar varios días. Son múltiples las universidades interesadas en asistir. De cada universidad se tiene el número de personas que la estará representando. Los organizadores del evento han decidido que cada día se dedicará a mostrar los resultados de una sola universidad y están interesados en que la mayor cantidad de universidades tengan su oportunidad. Sin embargo hay una regla especial que no se desea vulnerar: Si las universidades escogidas para participar en los días del $1$ al $k$ tienen cantidad de representantes $c_{1}, \ldots c_{k}$ entonces ha de cumplirse que la diferencia entre dos valores consecutivos $c_{i}$ y $c_{i+1}$ debe ser la misma.
El problema consiste en dado el conjunto de representantes de cada una de las universidades determinar cual es la mayor cantidad de días $k$ que puede durar el evento asegurando que la regla de los organizadores no se viole.
Input
La primera línea de la entrada contiene un entero $n (1 \leq n \leq 10000)$, la cantidad de universidades interesadas en participar en el evento.
La segunda línea de la entrada contiene $n$ enteros separados por espacio, el $i$-ésimo de ellos representa la cantidad de representantes $c_i (1 \leq c_i \leq 10^{9})$ de la $i$-ésima universidad.
Output
El valor requerido.