Recently a fruit startup known as FALHARI was pitched in Shark Tank India. Sharks didn't liked their idea and yet again Ashneer - one of the Sharks from Shark Tank Panel roasted the CEO of Falhari heavily. After working and fixing all the issues in there startup , The FALHARI guys got back to pitch their idea at Shark Tank, this time with a new CEO. The newly appointed CEO was none other than Ayush. This time Sharks liked the idea and were willing to invest in the idea with a condition that, Ayush will have to help them solve a puzzle.

There are N dishes arranged in a row in front of Ayush. The i-th dish from the left has A_i oranges on it.

Ayush will choose a triplet of integers (l, r, x) satisfying all of the following conditions:

• 1 ≤ l ≤ r ≤ N
• 1 ≤ x
• For every integer i between l and r (inclusive), x ≤ A_i​

He will then pick up and eat x oranges from each of the l-th through r-th dishes from the left.

At most how many oranges can he eat by choosing the triplet (l, r, x) to maximize this number?

Input:

• The first line of input contains the number of dishes.
• The next line contains N space-separated integers describing the number of oranges in i-th dish.

Output:

Print the maximum number of oranges Ayush can eat.

Constraints:

• 1 ≤ N ≤ 10⁴
• 1 ≤ A_i ​≤ 10⁵