Маяк 4. До закрытия шлюза
Экспедиция «МАЯК». Шлюз исследовательской базы закроется в момент x. Компьютер хранит время событий в отсортированном журнале; события с одинаковым временем возможны. Инженеру нужен номер самого позднего события, которое произошло именно до закрытия. Событие с отметкой ровно x уже не подходит.
Входные данные
В первой строке находятся n и x — количество записей и момент закрытия. Во второй строке — n временных отметок по неубыванию.
Выходные данные
Выведите индекс последнего события, произошедшего строго раньше x. Если ни одно событие не успело, выведите -1.
Ограничения
1 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены).
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| № | Входные данные | Выходные данные |
|
1
|
7 29
5 13 13 21 29 29 35
|
3
|
|
2
|
7 5
5 13 13 21 29 29 35
|
-1
|