Distance

You are given an array of integers. Choose two elements $a$ and $b$ from the array to maximize the value $r = a + b + d$, where $d$ is the distance between the two elements' positions in the array, that is, the absolute difference of their indices. The two elements may be the same; if you pick the same element twice, that distance is $0$. Find the maximum possible value of $r$.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) separated by spaces, where $a_i$ is the $i$-th element of the array.

Print a single integer, the maximum value of $r$.