난쿤이는 목이 마르다. 란이는 물이 든 컵 N개를 가지고 있다. 하지만 잔인한 란이는 난쿤이가 물 마시는 것에도 조건을 걸었다.

연속하고 양이 증가하는 컵들을 선택하여 마실 수 있는 것이다.

난쿤이는 가장 많은 물을 마시고싶어 한다. 여러분이 난쿤이를 도와주자.

예) 컵이 5개이고 각각 1, 4, 3, 2, 5 만큼 들어있다면

2,5의 양이 들어있는 컵을 선택하면 7만큼의 물을 마실 수 있다. 단 어떤 연속된 양이 증가하는 컵의 집합 한 개만 선택이 가능하다.

입력

• 첫째 줄에 컵의 수 N이 주어진다.(1<=N<=1,000,000)
• 둘째 줄에 각 컵에 든 물의 양이 공백으로 구분되어 주어진다. (0<물의 양<=1,000,000)

출력

입출력 예

입력

5 
1 4 3 2 5 

출력

7 

출처:ainta