Retângulo

Vô Pedro é um fazendeiro meticuloso. Em sua fazenda ele tem uma plantação no formato circular, com algumas árvores plantadas exatamente na circunferência da plantação. A figura (a) abaixo mostra a plantação com as árvores.

Agora vô Pedro quer usar uma longa corda e quatro das árvores para demarcar um retângulo na plantação, usando as árvores como vértices, com a corda marcando os lados. A figura (b) abaixo mostra dois retângulos que podem ser demarcados usando as árvores na plantação figura (a).

Dada a descrição das posições das árvores na plantação circular de vô Pedro, sua tarefa é determinar se é possível demarcar um retângulo conforme descrito acima.

Entrada

A primeira linha da entrada contém um inteiro N indicando o número de árvores na circunferência da plantação. As árvores são representadas como pontos na circunferência. A segunda linha contém N inteiros L₁, L₂, … L_N, indicando o comprimento do arco entre cada par de árvores consecutivas. Os arcos são dados no sentido anti-horário.

Saída

Restrições

• 4 ≤ N ≤ 10⁵
• 1 ≤ L_i ≤ 10⁶ para i = 1,2,…,N

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo 20 pontos, N ≤ 100.
• Para um conjunto de casos de testes valendo outros 20 pontos, N ≤ 300.
• Para um conjunto de casos de testes valendo outros 20 pontos, N ≤ 1000.
• Para um conjunto de casos de testes valendo outros 40 pontos, nenhuma restrição adicional.

Exemplos

8
3 3 4 2 6 2 2 2

S
	

4
14 16 15 15

N
	

6
3 7 7 3 10 10

S