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_1$, $L_2$, $\ldots$, $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

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 \leq N \leq 10^5$
• $1 \leq L_i \leq 10^6$ para $i = 1,2,\ldots ,N$

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $20$ pontos, $N \leq 100$.
• Para um conjunto de casos de testes valendo outros $20$ pontos, $N \leq 300$.
• Para um conjunto de casos de testes valendo outros $20$ pontos, $N \leq 1\ 000$.
• Para um conjunto de casos de testes valendo outros $40$ pontos, nenhuma restrição adicional.

Exemplos

Exemplo de entrada 1

8
3 3 4 2 6 2 2 2

Exemplo de saída 1

S

Exemplo de entrada 2

4
14 16 15 15

Exemplo de saída 2

N

Exemplo de entrada 3

6
3 7 7 3 10 10

Exemplo de saída 3

S