거리

면접 대비

시간 제한1초메모리 제한128 MB

요약

배열에서 같은 원소를 두 번 고를 수도 있을 때 두 값의 합에 위치 사이 거리를 더한 값을 최대화합니다.

난이도: 보통10점 중 5점
유형: 그리디, 배열
정답자: 아직 제출이 없습니다

문제

정수로 이루어진 배열이 주어진다. 이 배열에서 두 원소 $a$ 와 $b$ 를 골라 값 $r = a + b + d$ 를 최대로 만들고자 한다. 여기서 $d$ 는 두 원소의 배열 내 위치(인덱스) 사이의 거리, 즉 두 위치 번호의 차이의 절댓값이다. 두 원소가 서로 같아도 되며, 같은 원소를 두 번 고르면 그 거리는 $0$ 이다. $r$ 의 최댓값을 구하여라.

입력

첫째 줄에 배열의 원소 개수 $n$ ( $1 \le n \le 10^6$ )이 주어진다. 둘째 줄에 배열의 원소 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ )이 공백으로 구분되어 주어진다. 여기서 $a_i$ 는 배열의 $i$ 번째 원소이다.

출력

첫째 줄에 $r$ 의 최댓값을 정수 하나로 출력한다.

예제1

예제 1
입력
```
5
2 5 4 7 3
```
예상 출력
```
14
```