Максимальний мін-макс добуток
Limits: 2 sec., 256 MiB
У Зеника та Марічки є масив \(a\), що складається з \(n\) натуральних чисел.
Сьогодні вони дізналися про мін-макс добуток підмасиву, який визначено як добуток найменшого та найбільшого елементів цього підмасиву.
Тепер вони хочуть знайти максимальний мін-макс добуток, але тільки серед підмасивів, які містять щонайменше два елементи.
Допоможіть їм знайти це максимальне значення.
Input
У першому рядку задано одне ціле число \(n\) — розмір масиву.
У другому рядку задано \(n\) натуральних чисел \(a_i\) — елементи масиву.
Output
У єдиному рядку виведiть одне цiле число — вiдповiдь на задачу.
Constraints
\(2 \le n \le 4 \cdot 10^5\),
\(1 \le a_i \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 4 7 4 4 5 2 11 | 28 |
Notes
Підмасив — де довільна послідовність елементів масиву, що йдуть в ньому підряд.
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|