As we know, the majority of students in the world-class university like candy and game so much. With some candies, the students are playing a guessing game with you.

These students are standing in a line. Every student has some candies in the hand. (Of course the quantity of the candies will not be negative.) Some kindhearted students will tell you the exactly quantity of candies they have in hand, but some of them won't do that. You may think that THE GAME CAN'T PLAY, but the fact is, every student in line will tell you the exact total quantities of previous one (if exists), himself, and next one (if exists).

You should guess the maximum possible quantity the queried student might have.

The input will consist of multiple testcases.

The first line of each test case is an integer `n`, indicating the amount of students, 3 ≤ `n` ≤100000.

The second line contains `n` integers, the `i ^{th}` number

The third line also contains

The forth line contains an integer

提交代码