Один бинарный поиск на все случаи: предикат как параметр шаблона

Дан отсортированный по неубыванию массив и запросы четырёх видов:

• ge x: наименьший элемент ≥ x;
• gt x: наименьший элемент > x;
• le x: наибольший элемент ≤ x;
• cnt x: сколько раз x встречается.

Если нужного элемента нет, выведите none. Реализуйте одну шаблонную функцию template <class It, class Pred> It first_true(It first, It last, Pred p) (первая позиция, где монотонный предикат истинен) и выразите через неё все запросы с помощью лямбд.

Ввод: n (1 ≤ n ≤ 1500), массив, затем q (1 ≤ q ≤ 1500) и запросы. Значения по модулю до 10⁹.

Вывод: ответ на каждый запрос с новой строки.

Пример 1

Ввод:

5
1 3 3 5 9
4
ge 4
gt 3
le 0
cnt 3

Вывод:

5
5
none
2

Пример 2

Ввод:

1
7
4
ge 8
gt 6
le 7
cnt 1

Вывод:

none
7
7
0