거리

정수로 이루어진 배열이 주어진다. 이 배열에서 두 원소 $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$의 최댓값을 정수 하나로 출력한다.