\begin{tutorial}{Добуток}

\begin{enumerate}
\item Будемо перебирати перший мінімум, другий мінімум і розширяти відрізок, сумарно це все працюватиме не довше $O(n^3)$.
\item Будемо перебирати початок відрізка, далі будемо розширювати його вправо підтримуючи в std::multiset множину елементів, для кожної правої границі візьмемо з мультисета два мінімуми та порахуємо добуток. Таким чином ми переберемо кожен відрізок і порахуємо відповідь за $O(n^2 \cdot log(n))$.
\item Будемо робити все як в блоці 2, але мінімуми підтримуватимемо парою чисел.
\item Цей блок був створений для різноманітних евристик (переборів з відсіканням, чи чогось подібного).
\item Будемо перебирати другий мінімум. Для кожного числа порахуємо перше менше нього справа і зліва від нього - це можна зробити стеком. Потім для кожного другого мінімуму ми можемо взяти як перший мінімум або перше менше зліва, або справа, обидва взяти не можемо, візьмемо одне, а потім друге, опишемо процес з першим меншим зліва, справа буде симетрично. Нехай зараз ми розглядаємо $i$ - як другий мінімум. $l$ - індекс першого меншого зліва, $r$ - справа. На цей час ми визначились, що точно візьмемо $i$ та $l$, а отже відрізок $a[l,i]$. Тепер ми хочемо його максимально розширити так, щоб значення двох мінімумів не змінилось. Розширити вправо можна лише до $r$ виключно, оскільки з визначення $a_i>a_r$. Розширити вліво можна до першого меншого за $a_i$ виключно, серед тих, які лежать лівіше від позиції $i$, це ми можемо робити тримаючи останні дві позиції для кожного значення яке можуть приймати елементи масиву і будемо завдяки цьому шукати лівий кінець відрізка за $O(\sqrt{n})$ і тоді загальна складність алгоритму буде $O(n \cdot \sqrt{n})$.
\item Робитимемо все як в блоці 5, але пошук лівої границі можемо робити бін пошуком і sparse table, або деревом відрізків з каскадним спуском. Це працюватиме за $O(n \cdot log(n))$.
\end{enumerate}

Тут можна почитати як шукати найближчий менший елемент: https://bit.ly/3XIVqIj

Тут можна почитати про sparse table: bit.ly/3RcNFrm0

Тут можна почитати про дерево відрізків з каскадним спуском: bit.ly/3kKQ28J0


\end{tutorial}
