테라스 언덕
시간 제한1초메모리 제한1024 MB
일렬로 놓인 테라스 높이가 주어질 때, 사이의 모든 테라스가 더 낮은 같은 높이의 두 테라스 사이에 다리를 놓아 얻을 수 있는 최대 총 길이를 구한다.
문제
남반구 화성의 카리툼 산맥에 있는 지로티 언덕에서 탐사된 모든 산악 테라스는 특이한 성질을 지닌다. 크기가 거의 같고, 모두 가상의 직선 위에 놓여 있다.
테라스의 평평한 표면은 미래 주거 개발에 이상적이다. 테라스의 독특한 배치는 일부 테라스를 다리로 연결하는 대담한 공학 프로젝트를 가능하게 한다.
주변 지역의 상대적 지질 불안정성 때문에 다리로 연결된 두 테라스의 표면은 같은 높이여야 한다. 물론 두 테라스 사이의 모든 테라스 높이가 연결하려는 두 테라스의 높이보다 낮을 때만 두 테라스 사이에 다리를 놓을 수 있다.
프로젝트 엔지니어들은 지을 수 있는 모든 다리의 최대 총 길이를 알고 싶어 한다. 초기 계산을 단순화하기 위해 다음과 같이 가정한다. 이웃한 두 테라스 사이의 거리는 무시할 수 있을 만큼 작아서 모든 경우에 0으로 본다. 테라스의 너비는 1 길이 단위로 본다.
입력
첫째 줄에 테라스의 수 N (1 ≤ N ≤ 3 · 105)이 주어진다. 둘째 줄에 N개의 정수 a1, a2, . . . , aN (1 ≤ ai ≤ 106)이 주어지는데, ai는 i번째 테라스의 높이이다. 높이는 (가상의) 직선 위에서 테라스가 놓인 순서대로 주어진다.
출력
지을 수 있는 모든 다리의 최대 총 길이를 정수 하나로 출력한다.