Bonus: The Beauty and the Distance

hardPrefix SumGreedy

You are given an array of $$$n$$$ integers $$$b_1, b_2, ..., b_n$$$ representing the beauty values of sights at positions $$$1$$$ through $$$n$$$.

Choose two indices $$$l$$$ and $$$r$$$ such that $$$1 \le l < r \le n$$$ and the subarray $$$[l, r]$$$ contains at least 3 elements.

Find the maximum value of:

$$$$$$ b_{i_1} + b_{i_2} + b_{i_3} - (r - l) $$$$$$

where $$$i_1, i_2, i_3$$$ are indices of the three largest values in the subarray $$$[l, r]$$$.

Input Format:

The first line contains a single integer $n$ ($3 \le n \le 10^5$). The second line contains $n$ integers $b_1, b_2, ..., b_n$ ($1 \le b_i \le 10^8$).

Output Format:

Output a single integer --- the maximum possible value of the expression.

Examples:

Example 1:

Input:

6
9 8 7 6 5 4

Output:

22

Example 2:

Input:

5
5 1 4 2 3

Output:

8

Code

Loading Editor...