Розбір розв'язку

Наївний підхід — для кожного ~i~ шукати найближчий більший елемент прямим переглядом праворуч — працює за ~O(n^2)~ у найгіршому випадку (наприклад, коли масив відсортований за спаданням), що занадто повільно при ~n \le 2 \cdot 10^5~.

Ефективний розв'язок за ~O(n)~ використовує монотонний стек:

1. Проходимо масив справа наліво.
2. Підтримуємо стек індексів, у якому значення елементів строго спадають знизу догори (тобто на вершині стека завжди найменше з "кандидатів").
3. Для поточного індексу ~i~: поки на вершині стека лежить індекс ~j~, для якого ~a_j \le a_i~, знімаємо цей індекс зі стека (він більше нікому праворуч не знадобиться, оскільки ~a_i~ "закриває" його — будь-який елемент лівіше за ~i~, для якого ~a_j~ міг бути відповіддю, тепер знайде замість нього ~a_i~ або щось ще більше).
4. Якщо після цього стек порожній — відповідь для ~i~ дорівнює ~-1~; інакше відповідь — це індекс, що лежить на вершині стека (він і є найближчим більшим елементом праворуч).
5. Додаємо індекс ~i~ у стек і переходимо до наступного (лівішого) елемента.

Кожен індекс потрапляє в стек рівно один раз і виймається зі стека не більше одного разу, тож сумарна кількість операцій зі стеком — ~O(n)~, а отже й загальна складність усього алгоритму — ~O(n)~ за часом і ~O(n)~ за додатковою пам'яттю.