D - Black Widow

Languages: C, C++, Java, Python, C#
Time & Memory limits: (details)

Natalia Romanova a.k.a. Black Widow es una legendaria agente de S.H.I.E.L.D. Ella conoce decenas de idiomas y ha dominado el karate, el aikido, el jujitsu, el kung fu y varias técnicas soviéticas de autodefensa. Por otra parte, Natalia tiene capacidades mentales excepcionales y habilidades de actuación notables que la ayudan a recuperar la información incluso cuando ella es torturada.

La siguiente misión para Natalia es robar planos de la nueva arma secreta de Hidra. No era un gran problema para ella penetrar en la caja fuerte a través de los conductos de ventilación. Pero sólo es posible salir de la caja fuerte a través de un solo pasaje, desafortunadamente, donde están los sensores de presión en el piso colocados en varios puntos. Estos tienen una forma de segmentos entre paredes y dichos segmentos son ortogonales al pasaje. Por supuesto, Natalia tiene los planos del pasaje por lo que ella conoce la distancia a cada sensor. La Agente Romanova quiere pasar por el pasaje utilizando el método más rápido, es decir, haciendo una serie de backflips(Mortales hacia atrás). Sin embargo, la desventaja de este método es el hecho de que una distancia entre dos toques consecutivos de un piso (con las manos o los pies) es siempre la misma.

A pesar de todas sus habilidades Natalia no es una persona alta. ¿Cuál es la distancia mínima entre dos toques consecutivos de un piso que garantiza que Natalia no tocará ningún sensor?.

Input

La primera línea de la entrada contiene un número $N$ $(1 \leq N \leq 1000) $ que representa la cantidad de sensores en el pasaje.

La segunda línea de la entrada contiene $N$ números separados por espacios que representan la distancia entre el punto de inicio de Natalia y cada sensor. Cada distancia se encuentra entre 1 y $10^{9}$ inclusive.

Output

Imprima un entero - La menor distancia entre dos toques consecutivos del piso en los saltos de Natalia.

Sample test(s)

Input
5 1 3 4 8 10
Output
6
Input
10 2 3 5 10 12 15 20 30 44 63
Output
8