бинарный поиск

Реализуйте бинарный поиск на массиве чисел, отсортированном в неубывающем порядке.

Запрещается использование готовых функций бинарного поиска из стандартных библиотек.

В первой строке записано целое число nnn — количество чисел в массиве (1⩽n⩽3⋅1051 \leqslant n \leqslant 3 \cdot 10^51⩽n⩽3⋅105).

Во второй строке через пробел записаны nnn чисел массива. Все числа целые и принадлежат промежутку от −231-2^{31}−231 до 231−12^{31} - 1231−1 включительно. Числа в массиве упорядочены по неубыванию.

В третьей строке записано целое число kkk — количество запросов (1⩽k⩽3⋅1051 \leqslant k \leqslant 3 \cdot 10^51⩽k⩽3⋅105).

В четвёртой строке через пробел записаны kkk целых чисел-запросов из промежутка от −231-2^{31}−231 до 231−12^{31} - 1231−1 включительно.

Для каждого числа-запроса xxx в отдельной строке выведите через пробел числа bbb, lll и rrr, где bbb равно 111, если xxx присутствует в массиве, или 000 в противном случае; lll — индекс первого элемента, большего либо равного xxx; rrr — индекс первого элемента, большего xxx. Элементы массива нумеруются индексами от 000 до n−1n-1n−1.

Если подходящих элементов в массиве нет, договоримся, что возвращаемое значение будет равно nnn.