URI Online Judge | 2799

Northern Choir

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

There is a group of singers, residents of the northern region in Brazil, that are very famous by its interpretations of classic musics.

Each one of the members from this group has different vocal characteristics, such as the ease to reach high or low notes, agility on the notes scale, vibrato control, among others.

One of the most important characteristics is how many seconds the singer can sing the same note without losing his breath. When a singer loses his breath, it takes 1 second for him to recover himself.

The choir wants to sing a new song, in which there must always exist exactly 3 vocalists singing 3 notes at the same time. When a vocalist loses his breath, another vocalist must assume his place immediately, ensuring that the note keeps sounding. Another characteristic of this song is that all the vocalists must always give their best, or in other words, they must always sing until they are out of breath.

In order for the presentation to be short, the choir would like to sing this song in the lowest time possible, or in other words, the 3 notes must stop sounding at the same time and as soon as possible.

Given the amount of choir members, and the amount of time that each of them can sing without losing their breath, you must say what will be the duration of the song.


The first row will have an integer N, indicating how many singers are in Northern Choir (3 < N <= 20).

Following there will be N integers Fi, each one indicating how long a singer can sing without losing his breath (1 <= Fi <= 10, para todo 1 <= i <= N).


Your algorithm must print one row containing one integer D, indicating the duration of the presentation of the song.

Input Samples Output Samples

3 2 3 3


1 2 3 2 4


2 4 7 6 5