26638번 - Nowy kontrakt 다국어

Twoja firma, zajmująca się produkcją gier wideo, odniosła oszałamiający sukces – seria N gier o wędrującym przez Galaktykę pogromcy kwazarów sprzedała się znakomicie, przynosząc Ci sławę, pieniądze, a także niespodziewane kłopoty. Oto gruchnęła wieść, że znany pisarz science-fiction, na podstawie którego książek powstały Twoje gry, uznał właśnie, że prawa do adaptacji sprzedał po zbyt niskiej cenie i przez swoich prawników domaga się zmiany zapisów kontraktu.^∗

Umowa przewidywała, że za udzielenie licencji na grę numer i (gdzie i = 1, 2, . . . , N) pisarz otrzyma wynagrodzenie a_i, będące pewną liczbą całkowitą dodatnią. Prawnicy argumentują jednak, że skoro każda następna gra sprzedawała się lepiej niż poprzednia, także wynagrodzenie powinno być wyższe. Chcesz uniknąć niepotrzebnego rozgłosu (a także paniki wśród akcjonariuszy), zatem ingerencja w zapis umowy powinna być jak najmniejsza. Zdecydowałeś się zatem do każdej z liczb a₁, . . . , a_N dopisać pewną liczbę cyfr na końcu tak, aby otrzymany w ten sposób nowy ciąg był ściśle rosnący. Dla każdego a_i dopisane cyfry (oraz ich liczba) mogą być inne, możesz też niektórych liczb nie zmieniać w ogóle.

Rozstrzygnij, ile minimalnie cyfr musisz w tym celu łącznie dopisać.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N (1 ≤ N ≤ 200 000). W kolejnych N wierszach podane są liczby całkowite a₁, . . . , a_N (1 ≤ a_i ≤ 10⁹).

Twój program powinien wypisać na wyjście jedną liczbę całkowitą – minimalną możliwą liczbę dopisanych cyfr.

Wyjaśnienie do przykładu: Dopisując, odpowiednio, cyfry 7 i 3 do drugiej i trzeciej liczby otrzymamy rosnący ciąg (8, 57, 133). Możliwe są inne rozwiązania, ale nie da się osiągnąć celu przez dopisanie tylko jednej cyfry.