Changes in Club Membership

Spring is the season of farewells and new beginnings. This year, too, the long-standing Geigaku Club is about to add a new name to its history.

The club's activity log records how the membership changed over n years. According to the log, the number of members before the first year was 0. Each year, only first-year students join, in April. Members leave only in March, three years after they joined, when they graduate.

To trace how the club changed, use the number of new members in each of the n years to find the number of members in the year when the enrolled membership was largest.

The input consists of multiple datasets. There are no more than 50 datasets. Each dataset has the following format.

n a1 a2 ... an

n is the number of years for which new members are recorded, an integer from 3 to 1000. The next line contains n integers giving the number of new members in each year. The number of new members $a_i$ in the i-th year satisfies $0 \le a_i \le 10^8$.

The input ends with a line containing a single zero.

For each dataset, print on one line the number of members in the year when the enrolled membership was largest.