Максимальний мін-макс добуток

Обмеження: 2 сек., 256 МіБ

У Зеника та Марічки є масив \(a\), що складається з \(n\) натуральних чисел.

Сьогодні вони дізналися про мін-макс добуток підмасиву, який визначено як добуток найменшого та найбільшого елементів цього підмасиву.

Тепер вони хочуть знайти максимальний мін-макс добуток, але тільки серед підмасивів, які містять щонайменше два елементи.

Допоможіть їм знайти це максимальне значення.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — розмір масиву.

У другому рядку задано \(n\) натуральних чисел \(a_i\) — елементи масиву.

Вихідні дані

У єдиному рядку виведiть одне цiле число — вiдповiдь на задачу.

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 7 4 4 5 2 11	28

Примітки

Підмасив — де довільна послідовність елементів масиву, що йдуть в ньому підряд.