Для каждого $$$a_i$$$ посчитаем количество чисел левее и не больше нас, а так же чисел правее и не меньше нас. Если же первое количество больше или равно второму, то выводим ответ. Но такое решение работает за $$$O(N^2)$$$, что приводит к превышению времени работы.
Давайте ускорим решение, будем поддерживать нужные множества чисел слева от текущего числа и справа. Когда переходим к соседнему числу, то перекидываем из правого множества, число в левое. Если наше множество сможет за быстро говорить, сколько чисел больше заданного числа, то мы решили нашу задачу. В качестве таких множеств, можно взять декартовое дерево, или множества с порядковой статистикой, которое есть в C++.
