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₁, A₂, A₃,…,A_N-2,A_N-1, A_N, o perfil definido será chamado de perfil Escher se tivermos A₁+A_N igual a A₂+A_N-1 igual a A₃+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 ≤ i ≤ 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 ≤ N ≤ 10000.
• 1 ≤ A_i ≤ 1000, para todo 1 ≤ i ≤ 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

Exemplos

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

S
	

5
2 1 9 13 12

N