Zadanie

Hranatý plot

Počet bodov: 50

Mám fajný plot z \(N\) dosák. \(i\)-ta doska je meter široká, a \(V_i\) centimetrov vysoká.

Mám fajný štetec, meter široký. Jedným ťahom štetca viem nalakovať horizontálny alebo vertikálny pás meter široký, a ľubovoľne dlhý - musí však byť spojitý, teda neprechádzať cez vzduch a nepreskakujúc dosky.

Nechcem žiadnu časť plota nalakovať viac ako raz (ako som začul mladšiu generáciu, bol by som potom an-laky). Koľko najmenej ťahov štetca musím spraviť?

Vstup a Výstup

V prvom riadku je \(N\). V druhom riadku je \(N\) celých čísel \(V_i\).

V prvej sade \(1 \leq N, V_i \leq 100\).

V druhej sade \(1 \leq N \leq 3000\), \(1 \leq V_i \leq 10^9\).

Príklady

Input:

1
47

Output:

1

nalakujem dosku vertikálne

Input:

5
1 2 8 2 1

Output:

3

horizontálny pás naspodku, potom další od 2ej do 4ej dosky, a nakoniec nalakujem zvyšok tretej

Input:

5
2 1 8 1 2

Output:

4

horizontálny pás, a potom nalakujem 1u, 3u a 5tu dosku