| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 (추가 시간 없음) | 1024 MB | 74 | 46 | 32 | 56.140% |
Bajtek w końcu kupił sobie wodoodporny smartwatch. Od razu poszedł na basen, by sprawdzić czy działa. Okazało się, że zegarek jest dość dziwny. W różnych momentach zapisywał on jak daleko Bajtek był od początku basenu, tj. od brzegu, z którego wystartował. Bajtek odczytał ciąg kolejnych zarejestrowanych odległości z zegarka, nie bardzo rozumie jednak, jak zinterpretować ten wynik. Chciałby się dowiedzieć, ile minimalnie długości basenu przepłynął. Możesz założyć, że Bajtek zawracał jedynie po dopłynięciu do końca basenu oraz zaczynał od brzegu i kończył przy brzegu (choć nie musiał tego zarejestrować zegarek). Bajtek mógł się także czasami zatrzymywać dla odpoczynku, niekoniecznie przy brzegu basenu.
Napisz program, który: wczyta odczyty zegarka Bajtka, wyznaczy minimalną możliwą liczbę długości basenu, jakie przepłynął Bajtek i wypisze wynik na standardowe wyjście.
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, 1 ≤ N ≤ 1 000 000, określająca liczbę odczytów zegarka Bajtka. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb całkowitych P1, P2,. . . , PN , 0 ≤ Pi ≤ 109, określających kolejne odległości od pewnego ustalonego brzegu basenu. Możesz założyć, że co najmniej jedna liczba pośród P1, P2,. . . , PN nie będzie zerem.
W pierwszym (jedynym) wierszu wyjścia powinna być jedna liczba całkowita – minimalna liczba długości basenu jakie przepłynął Bajtek.
7 3 7 11 11 6 2 4
3
Wyjaśnienie do przykładu: Podczas przepłynięcia pierwszej długości zegarek mógł zarejestrować następujące odległości od brzegu: 3, 7 oraz 11 (dwukrotnie, bo tam się mógł zatrzymać Bajtek). Drugi basen to odległości 6 i 2, a odczyt z trzeciej, ostatniej długości basenu to 4. Zauważ, że nie jest to jedyna możliwość. Zegarek mógł także zarejestrować 3 oraz 7 podczas pierwszej długości basenu, 11, 11 oraz 6 podczas drugiej, a 2 i 4 podczas trzeciej długości. Nie jest jednak możliwe, aby Bajtek przepłynął mniej niż trzy długości basenu.
9 1 2 3 4 5 4 3 2 1
2
6 28 28 28 28 28 28
1