Stay for a Song - Repovive Starter Round 8 | Repovive

23B. Stay for a Song

1000 pts1s256 MB

A radio station plays $n$ songs in a fixed order, repeating the playlist forever. The song durations are $a_1, a_2, \ldots, a_n$ seconds. There are no gaps between songs, including between song $n$ and song $1$ .

You turn on the radio at an arbitrary moment, possibly in the middle of a song. This moment is not necessarily an integer number of seconds.

Find the smallest integer $T$ such that listening continuously for $T$ seconds guarantees that you hear at least one complete song, regardless of when you turn on the radio.

A song counts only if you hear one playback of it from its beginning to its end. A playback starting exactly when you turn on the radio or ending exactly when you stop listening also counts.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

Input

n

a_1 \quad a_2 \quad \ldots \quad a_n

The first line contains the number of songs $n$ .

The second line contains their durations in playback order.

Output

T

Print the smallest integer listening duration that guarantees hearing a complete song.

Samples

Input

4
4 2 7 3

Explanation

Listening for 9 seconds is insufficient: if you join half a second after the third song starts, you need 6.5 more seconds for it to finish and then 3 seconds to hear the fourth song completely. This takes 9.5 seconds in total.

Listening for 10 seconds always allows you to hear a complete song, regardless of when you join.

Output

Input

1
6

Explanation

The same 6-second song repeats forever. If you join half a second after a playback starts, you must wait 5.5 seconds for that playback to finish and then listen to the next playback for 6 seconds. Thus, 11 seconds are insufficient, while 12 seconds always suffice.

Output

Input

4
8 1 2 7

Explanation

The first song starts again immediately after the fourth song ends. If you join half a second after the fourth song starts, you need 6.5 more seconds for it to finish and then 8 seconds to hear the first song completely. This takes 14.5 seconds, so 14 seconds are insufficient.

Listening for 15 seconds always allows you to hear a complete song.

Output

You turn on the radio at an arbitrary moment, possibly in the middle of a song. This moment is not necessarily an integer number of seconds.

Find the smallest integer $T$ such that listening continuously for $T$ seconds guarantees that you hear at least one complete song, regardless of when you turn on the radio.

A song counts only if you hear one playback of it from its beginning to its end. A playback starting exactly when you turn on the radio or ending exactly when you stop listening also counts.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

n

a_1 \quad a_2 \quad \ldots \quad a_n

The first line contains the number of songs $n$ .

The second line contains their durations in playback order.

T

Print the smallest integer listening duration that guarantees hearing a complete song.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

23B. Stay for a Song

Constraints

Input

Output

Samples

23B. Stay for a Song

Constraints

Input

Output

Samples