Maximize Score by Reversal and Contiguous Equal Subarray

Given an array of $n$ positive integers $a_1, a_2, \dots, a_n$, you are allowed to perform one reversal on a contiguous subarray. Specifically, if you reverse the segment $a_l, a_{l+1}, \dots, a_r$, the array becomes:

$$a_1, a_2, \dots, a_{l-1}, a_r, a_{r-1}, \dots, a_l, a_{r+1}, \dots, a_n$$

After the reversal, you may choose any contiguous segment in the resulting array that consists entirely of equal numbers. The score of such a segment is defined as:

$$ (r - l + 1) \times a_l $$

Your task is to determine the maximum possible score that can be obtained after performing the reversal operation.

inputFormat

The first line contains a single integer $n$ representing the length of the array.

The second line contains $n$ space-separated positive integers $a_1, a_2, \dots, a_n$.

outputFormat

Output a single integer representing the maximum score that can be obtained after performing one reversal operation.

sample

5
1 3 3 3 2

9