Привет, codeforces!
У меня вопрос:
Если у нас есть массив $$$a$$$ длины $$$n$$$ (не обязательно перестановка), $$$L_i$$$ — индекс ближайшего слева от $$$i$$$ элемента массива, который $$$≥$$$ чем $$$a_i$$$, а $$$R_i$$$ — индекс ближайшего $$$>$$$ (строго большего!) справа, то какая хорошая оценка сверху на: $$$\sum\limits_{i=1}^n min(i - L_i, R_i - i)$$$?
Я знаю, что если $$$R_i$$$ — больше или равный, то это $$$O(n log n)$$$.
Буду рад услышать ваши ответы!