Hide

Problem E
Hópavinna

Languages en is

In the next iteration of ÁFLV, the course will make use of group assignments to evaluate students’ knowledge. As a student, you are seeking to minimize the amount of time spent on doing the assignments while still getting your desired grade. This will allow you to spend more time partying!

You have found a great partner, Grimmhildur, for the assignments. She does not mind doing the majority of the workload. She will even handle an assignment by herself on occasion, meanwhile you spend your time visiting Lebowski’s Bar with the student union. Therefore, you can choose to skip participation in some assignments, but still receive the grade for it. However, if you skip two consecutive assignments, she will report you as a passenger to the instructors and you will fail the course.

You have an estimate of the number of minutes you would need to spend on each assignment, should you participate in it. If you do not participate in an assignment, then you spend $0$ minutes on that assignment and instead get to party! What is the minimum number of minutes you need to spend on assignments to pass the course?

Input

The first line contains an integer $n$, the number of group assignments. The next line contains $n$ integers, $a_1, \dotsc , a_ n$, the number of minutes you would spend on assignment $i$, if you participate in it. For all $a_ i$, where $1 \leq i \leq n$, it is guaranteed that $0 \leq a_ i \leq 1000$.

Output

Output one line with one integer, the desired answer as described above.

Scoring

Group

Points

Constraints

1

30

$1 \leq n \leq 5$

2

30

$1 \leq n \leq 20$

3

40

$1 \leq n \leq 10^5$

Sample Input 1 Sample Output 1
2
12 13
12
Sample Input 2 Sample Output 2
5
11 4 1 20 13
18
Sample Input 3 Sample Output 3
9
4 5 4 5 1 5 4 5 4
17