Apteka
Limit pamięci: 32 MB
Jaś stoi ostatni w kolejce do apteki. Ponieważ Jasiowi bardzo się śpieszy, to postanowił, że spróbuje się pozamieniać miejscami z niektórymi osobami, nawet jeśli musiałby za to zapłacić.
Każda osoba jest chętna do zamiany, ale -tej osobie za przesunięcie o każde jedno miejsce dalej w kolejce trzeba zapłacić . Dokładniej, jeśli Jaś jest miejsc () dalej od kasy niż pewna osoba i jeśli chce się z nią zamienić miejscami, to musi jej zapłacić kwotę .
Jaś chciałby być pierwszy w kolejce i zastanawia się, jak dokonywać zamian, aby wydać jak najmniej.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę osób, które stoją przed Jasiem w kolejce do apteki.
Następny wiersz wejścia zawiera liczb całkowitych (), gdzie oznacza kwotę, jaką Jaś musi zapłacić -tej osobie za przesunięcie o każde miejsce dalej w kolejce. Kolejność osób liczona jest od osoby, za którą bezpośrednio stoi Jaś, a więc od końca kolejki do jej początku.
Możesz założyć, że w przynajmniej przypadków testowych zachodzi warunek: .
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej kwocie, jaką Jaś musi zapłacić, aby być pierwszym w kolejce.
Przykład
Dla danych wejściowych:
4
5 2 4 3
poprawną odpowiedzią jest:
10
Wyjaśnienie do przykładu:
Jaś zamieni się najpierw z osobą w kolejce za kwotę , a następnie z pierwszą osobą w kolejce za kwotę .
Autor zadania: Jacek Tomasiewicz.