El pirata Jeremías planea ofrecer un espectáculo a su tripulación. Para ello, Jeremías dispone de N loros, que planea equilibrar sobre sus hombros. Cada uno de los N loros tiene un peso, en gramos, que Jeremías conoce de antemano.

Jeremías tiene solamente dos hombros, y por lo tanto debe separar los loros en dos grupos. El desbalance del Jeremías sera igual a la diferencia (positiva) de peso entre el grupo que lleva en el hombro izquierdo y el que lleva en el hombro derecho.

¿Cuál es el menor valor que puede tomar el desbalance del pirata?

Input

La entrada comienza con una línea que contiene un único entero, N (0 <= N <= 10000)

Las siguientes N líneas describen los pesos de los loros. Cada línea contiene un único entero w_i (0 <= w_i <= 1000)

Output

Una línea con un único entero, el mínimo desbalance (en valor absoluto).

Example

Input:
4
2 1 5 3
Output:
1