XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: retangulo.x, onde x deve ser c, cpp, java, js ou py

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 L1, L2, … LN, indicando o comprimento do arco entre cada par de árvores consecutivas. Os arcos são dados no sentido anti-horário.

Saída

Seu programa deve produzir uma única linha, contendo um único caractere, que deve ser S se é possível demarcar um retângulo usando as árvores como vértices, ou N caso contrário.

Restrições

  • 4 ≤ N ≤ 105
  • 1 ≤ Li ≤ 106 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

Entrada
8
3 3 4 2 6 2 2 2
Saída
S
	

 

Entrada
4
14 16 15 15
Saída
N
	

 

Entrada
6
3 7 7 3 10 10
Saída
S
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação