Problem description

Back
Show PDF
Pudełka
(O)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Jasio ma N pudełek ułożonych w koło. W i‑tym pudełku znajduje się Ai krasnali.

W jednym ruchu Jasio wybiera jedno pudełko — załóżmy, że ma ono numer i. Następnie dla każdego j ∈ {1, 2, …, N} zabiera j krasnali z pudełka o numerze i + j. Pudełka są ułożone w koło, więc utożsamiamy pudełko o numerze k z pudełkiem o numerze k + N.

Zatem po takiej operacji:

  • z pudełka o numerze i + 1 zniknie 1 krasnal,
  • w pudełku i + 2 będą 2 krasnale mniej,
  • …
  • z pudełka i zostanie zabrane N krasnali.

Jasio nie może wykonać ruchu, jeśli któreś z pudełek nie zawiera wystarczająco wielu krasnali.

Twoim zadaniem jest napisanie programu, który rozstrzygnie, czy Jasio może wykonać pewną liczbę ruchów tak, aby na końcu wszystkie pudełka były puste.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N — liczba pudełek.

W drugim wierszu wejścia znajduje się N liczb całkowitych A1, A2, …, AN — liczby krasnali w kolejnych pudełkach.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno się znaleźć jedno słowo:

  • TAK, jeśli Jasio może opróżnić wszystkie pudełka pewnym ciągiem ruchów,
  • NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Ai ≤ 109.

Przykłady

Wejście Wyjście Wyjaśnienie 
5
4 5 1 2 3

TAK

Jasio może wykonać jeden ruch — wybrać drugie pudełko. Wtedy z trzeciego pudełka zostanie zabrany jeden krasnal, z czwartego dwa, a ostatecznie z drugiego pudełka zostanie zabranych pięć krasnali.
Wejście Wyjście Wyjaśnienie 
5
6 9 12 10 8

TAK

Jasio może wykonać trzy ruchy — wybrać trzecie, czwarte i piąte pudełko.
Wejście Wyjście 
4
1 2 3 1

NIE