Candies for the Olympiad

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Before today’s Olympiad, Marichka dropped by the "Roshan" sweet shop. She believes that candies will help her solve problems better and faster.

There are \(n\) types of candies in the shop. The sweetness of the \(i\)-th type of candy is \(a_i\).

Marichka only has enough money for two types of candies because she is helping Algotester raise funds for drones for the Armed Forces of Ukraine.

Marichka thinks that if she eats the \(i\)-th type of candy first and then the \(j\)-th type during the Olympiad, their problem-solving efficiency will be \((a_i + j) - (a_j + i)\). Note that the order of eating matters. If she eats them in the opposite order — the \(j\)-th type of candy first, and then the \(i\)-th type — the efficiency might be different.

What is the maximum efficiency Marichka can achieve by purchasing two types of candies?

Input

The first line contains an integer \(n\) — the number of candy types.

The next line contains \(n\) integers \(a_i\) — the sweetness of the \(i\)-th type of candy.

Output

In a single line, output the maximum efficiency of the candies.

Constraints

\(2 \le n \le 4 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Problem evaluation consists of the following subtasks:

1 point — example from the statement,

19 points — \(n \le 1000\),

5 points — no additional constraints.

You will receive the points for a subtask only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 5 2 7 44	40

Notes

In the example, Marichka can choose \(i=5\) and \(j=3\). Then the efficiency of the candies will be \((a_5+3)-(a_3+5)=(44+3)-(2+5)=40\).