Заметим, что из подотрезка массива можно составить многоугольник, если удвоенный максимум на отрезке меньше суммы на отрезке.

\textbf{ Подгруппы 1, 2 ($N \leq 5000$). }

Перебираем левую и правую границы, поддерживаем сумму и максимум. Время $O(n^2)$.

\textbf{ Подгруппа 3 ($a_i\le a_{i+1}$). }

Максимум это всегда самый правый элемент отрезка, поэтому можно зафиксировать правую границу отрезка и искать подходящие левые границы бинарным поиском с префиксными суммами. Время $\mathcal{O}(n \cdot \log n)$.

\textbf{ Подгруппа 4 (массив случайно перемешан). }

Находим максимум в массиве. Рекурсивно решаем задачу на массиве всех элементов левее максимум, аналогично решаем на массиве правее максимума.

Теперь нужно посчитать количество хороших отрезков, содержащих максимум. Для этого нужно найти для каждой правой границы минимальную подходящую левую, что можно делать методом двух указателей.

Так как максимум каждый раз делит массив примерно поровну, то решение работает за $\mathcal{O}(n \cdot \log n)$ ожидаемо. Заметим, что оценка времени работы в этом алгоритме такая же, как в алгоритме QuickSort.

\textbf{ Полное решение. }

Воспользуемся техникой <<разделяй и властвуй>>.

Рекурсивно делим массив пополам: ответ = левая часть + правая часть + отрезки, пересекающие середину.

Посчитаем все отрезки, которые пересекают середину и в которых максимум находится в левой части, отрезки с максимумом в правой части рассматриваются аналогично.

Если мы переберем левую границу отрезка, то на правую границу наложены всего два ограничения: во первых правая граница должна быть достаточно большой, что бы сумма превосходила два максимума, но не настолько большой, что бы максимум в правой части отрезка превзошел максимум в левой части. Эти две границы можно искать бинарным поиском. После нахождения границ пересчитываем ответ.

Время работы: $\mathcal{O}(n \cdot \log^2 n)$.
