26675번 - Punkty rankingowe 스페셜 저지다국어

Bajtek postanowił sumiennie przygotować się do tegorocznych Potyczek Algorytmicznych. W tym celu założył konto na portalu BitForces, na którym regularnie odbywają się zawody programistyczne.

Bajtek zorientował się, że portal stosuje system punktów rankingowych (tzw. rating), dzięki któremu może on śledzić własne postępy w porównaniu z osiągnięciami innych zawodników. Ranking zawodnika jest liczbą całkowitą (być może ujemną). Tuż po założeniu konta ranking Bajtka wynosił 0, a każde zawody programistyczne, w których uczestniczył, zwiększały lub zmniejszały jego ranking o pewną liczbę całkowitą. Co więcej, w portalu dostępna jest cała historia zmian rankingu po każdych zawodach. Podekscytowany Bajtek zabrał się do analizy tych danych. Zapisał on na kartce kolejno n liczb:

• największy wzrost rankingu, jaki nastąpił w pojedynczych zawodach;
• największy łączny wzrost rankingu w dwóch kolejnych zawodach;
• największy łączny wzrost rankingu w trzech kolejnych zawodach;
• itd., aż ostatecznie zapisał największy łączny wzrost rankingu w n kolejnych zawodach.

Kilka dni później Bajtek chciał sobie przypomnieć ciąg zmian rankingu. Okazało się jednak, że portal BitForces ma akurat problemy techniczne. . . Czy pomożesz Bajtkowi i odzyskasz jakikolwiek poprawny ciąg zmian rankingu o długości co najmniej n, który jest zgodny z danymi zapisanymi na kartce?

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 300) odpowiadającą liczbie informacji spisanych przez Bajtka na kartce. Drugi wiersz zawiera n liczb całkowitych a₁, a₂, . . . , a_n (−10⁶ ≤ a_i ≤ 10⁶) znajdujących się na kartce Bajtka. Dla każdego 1 ≤ j ≤ n, największy łączny wzrost rankingu, jaki nastąpił w przeciągu j kolejnych zawodów, jest według Bajtka równy dokładnie aj.

Jeśli istnieje ciąg zmian rankingu spełniający wszystkie warunki opisane w treści zadania, w pierwszym wierszu wejścia wypisz słowo TAK. Następnie podaj przykładowy ciąg zmian. W drugim wierszu wyjścia wypisz długość znalezionego ciągu k (n ≤ k ≤ 100 000), a w trzecim wierszu – kolejne elementy tego ciągu b₁, b₂, . . . , b_k (−10¹³ ≤ b_i ≤ 10¹³).

Jeśli istnieje wiele poprawnych rozwiązań, wypisz dowolne z nich. Jeśli natomiast zadany ciąg zmian nie istnieje, wypisz NIE w pierwszym i jedynym wierszu wyjścia.

Można udowodnić, że jeżeli dla danych wejściowych spełniających ograniczenia istnieje jakikolwiek poprawny ciąg zmian, to istnieje też poprawny ciąg zmian spełniający powyższe ograniczenia.

Poniżej przedstawiony jest ciąg zmian z zaznaczonymi największymi wzrostami rankingu w jednych, dwóch, trzech i czterech kolejnych zawodach: