Автокомментарий: текст был обновлен пользователем Tigutor (предыдущая версия, новая версия, сравнить).

Ближайший справа или слева? Или сразу с двух сторон нужно найти такой элемент, что $$$|\text{pos}-i|$$$ минимально и $$$a_i \ge x$$$?

Пусть решаем задачу вправо. Задача влево — зеркальная. Не используя рекурсии, можно подниматься от листа в дереве отрезков, соответствующего отрезку $$$\left[p,p\right]$$$ до тех пор, пока мы не найдем первого предка, левая граница которого не меньше $$$p$$$ и максимум на нем больше $$$x$$$. С этого момента начинаем спускаться от предка, в котором остановились, в другой лист, выбирая каждый раз, пойдем направо или налево. Если максимум слева $$$\ge x$$$, то идем влево, иначе — вправо. Придем в листовую вершину, для которой максимум $$$\ge x$$$, индекс в ней и будет ответом. Если запутались, то нарисуйте на бумаге дерево отрезков для массива из $$$16$$$ элементов, и попробуйте поподниматься от листьев и спускаться к листьям. Асимптотика $$$O(\log(n))$$$ на запрос, так как мы пройдем не больше чем удвоенная высота.

Эта задача, опять же, является древним баяном, и сдать ее можно здесь.