Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2025
Problem description
Krasnal Alpinek wybrał się na wycieczkę w góry. Tym razem jego trasa wiodła wzdłuż całej długości szlaku, który przechodził kolejno przez N szczytów. Na każdym z nich znajdował się punkt widokowy, a na nim tablica informacyjna dotycząca szczytu.
Niestety, podczas wyprawy Alpinka okazało się, że ktoś złośliwie zamazał wysokości wszystkich szczytów na tablicach, zastępując je wymyślonym przez siebie współczynnikiem atrakcyjności szczytu. Współczynnik ten oznaczał sumę wysokości trzech szczytów: szczytu na którym znajdowała się tabliczka, najwyższego szczytu na szlaku w kierunku jego początku oraz najwyższego szczytu na szlaku w kierunku jego końca.
Alpinek postanowił poszukać informacji na temat wysokości konkretnych szczytów u mieszkańców leżącej nieopodal wioski. Jednakże jedyną rzeczą, o której się dowiedział, było to, który ze szczytów jest najwyższy oraz jaka jest jego wysokość. Upewnił się on też, że najwyższy szczyt jest tylko jeden, więc wszystkie pozostałe szczyty są od niego ściśle niższe.
Alpinek próbuje teraz dociec na podstawie zebranych informacji jakie są wysokości kolejnych szczytów. Czy jesteś w stanie mu pomóc?
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę szczytów na trasie Alpinka.
W drugim wierszu wejścia znajduje się N oddzielonych pojedynczymi odstępami liczb całkowitych si, gdzie si oznacza współczynnik atrakcyjności i-tego w kolejności szczytu. Formalniej, gdyby wysokości kolejnych szczytów wynosiły kolejno a1, a2, …, aN, to zachodzi $s_i = \max\limits_{\ 1 \leq j \leq i-1} \{a_j\} + a_i + \max\limits_{\ i+1 \leq j \leq N} \{a_j\}$.
Możesz założyć, że wysokość każdego szczytu jest dodatnią liczbą całkowitą nie większą niż 108. Przyjmujemy umownie, że wysokości najwyższych szczytów na szlaku przed pierwszym szczytem oraz za ostatnim szczytem wynoszą 0.
W trzecim i ostatnim wierszu wejścia znajdują się dwie oddzielone pojedynczym odstępem liczby całkowite k oraz ak, oznaczające kolejno pozycję oraz wysokość najwyższego szczytu na trasie.
Wyjście
Na wyjściu wypisz N liczb a1, a2, …, aN oznaczających wysokości kolejnych szczytów, spełniających wszystkie warunki podane w treści oraz na wejściu. Możesz założyć, że dla ciągu podanego na wejściu istnieje dokładnie jedna taka odpowiedź.
Ograniczenia
1 ≤ N ≤ 106, 1 ≤ si ≤ 3 ⋅ 108, 1 ≤ k ≤ N, 1 ≤ ak ≤ 108.
Przykłady
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|