Escher

M. C. Escher foi um artista gráfico holandês que fazia incríveis ilustrações onde preenchia a tela com objetos auto-similares, cujos contornos encaixam neles próprios, criando simetrias geométricas muito impressionantes. Veja um exemplo dessa ideia na figura, que mostra um objeto que é um perfil ortogonal definido por uma sequência de números naturais representando a sequência de alturas. Podemos pegar uma cópia do objeto, rotacionar $180$ graus e encaixar perfeitamente no objeto original, formando um retângulo.

Em termos mais gerais, se uma sequência de N números naturais representando a sequência de alturas for $A_1, A_2, A_3, \ldots, A_{N-2}, A_{N-1}, A_N$, o perfil definido será chamado de perfil Escher se tivermos $A_1 + A_N$ igual a $A_2 + A_{N-1}$ igual a $A_3 + A_{N-2}$, e assim por diante. Neste problema, será dada a sequência de alturas que definem o perfil e seu programa deve decidir se o perfil é Escher, ou não.

Entrada

A primeira linha da entrada contém um número $N$, indicando quantos números tem a sequência. A segunda linha da entrada contém $N$ números naturais, $A_i$, para $1 \leq i \leq N$, definindo a sequência de alturas do perfil.

Saída

Seu programa deve imprimir uma linha contendo o caractere S, se o perfil for Escher; ou N, senão.

Restrições

• $3\leq N\leq 10\ 000$.
• $1\leq A_i\leq 1\ 000$, para todo $1\leq i\leq N$.

Informações sobre a pontuação

• Em um conjunto de casos de teste somando $20$ pontos, $N = 3$.
• Em um conjunto de casos de teste somando $80$ pontos, nenhuma restrição adicional.

Exemplos

Exemplo de entrada 1

12
3 6 6 4 3 2 8 7 6 4 4 7

Exemplo de saída 1

S

Exemplo de entrada 2

5
2 1 9 13 12

Exemplo de saída 2

N