Поиск в массиве целых чисел в определенном диапазоне

Может ли кто-нибудь подсказать мне решение следующей задачи?

Даны массив ar[] длины n и несколько запросов, каждый из которых имеет вид a, b, c, найдите число с наименьшим индексом i такое, что индекс лежит в диапазоне [c, n] и такое, что a < ar[i] < b. Всего существует (n - 1), c переходит из 1 в n - 1. Ожидаемая сложность для каждого запроса должна быть около O(log n), и подходит предварительное вычисление сложности не более O(n log n) . Интуитивно мне пришло в голову дерево сегментов, но я не мог придумать, как его построить и что хранить в каждом узле.