Є \(N\) страв, які розташовані в ряд перед Степаном. \(I\)-та страва має \(A_i\) апельсини на ній. Степан вибере трійку цілих чисел (\(l, r, x\)), що задовольняє всім наступним умовам:

• \(1\leq l \leq r \leq N\);

• \(1 \le x\);

• для кожного цілого числа \(i\) між \(l\) і \(r\) (включно), \(x \le A_i\).

Потім він візьме та з’їсть \(x\) апельсинів з кожної від \(l\)-ї по \(r\)-у страву.

Скільки всього апельсинів він може з’їсти, вибравши так трійку (\(l, r, x\)), щоб з'їсти побільше цих фруктів?

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 10^4\))

Наступний  рядок містить \(N\) цілих чисел \(A_i\) (\(1 \le A_i \le 10^5\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану кількість апельсинів.

Примітка

До прикладу 1:

Вибравши (l,r,x)=(2,6,4), він може з’їсти 20 апельсинів.

Приклад вхідних даних

6
2 4 4 9 4 9

Приклад вихідних даних

20

Приклад вхідних даних

6
200 4 4 9 4 9

Приклад вихідних даних

200