Леді дуже довго відкладала кошти на те, щоб купити собі магічний набір відрізків. Набір називається магічним, якщо у наборі рівно відрізків та кожна пара відрізків має спільну точку.
Коли вона назбирала необхідну суму та купила набір, відразу ж вирішила пограти з ним. Це було просто неймовірно! Але сталося те, чого вона ніяк не могла передбачити: коли вона пішла їсти, її маленька сестра Марічка підкинула туди ще один відрізок та перемішала набір, то ж Леді не знає, який саме відрізок підкинула Марічка. Вона дуже розізлилася на сестру, але що поробиш – доведеться видалити з набору один відрізок, щоб той знову став магічним.
Вам, як найкращому програмісту в світі, Леді пропонує написати програму, яка за заданим числом та відрізками, що лежать перед нею, визначить, який саме відрізок треба видалити.
У першому рядку задається єдине число (1 \le N \le 10^5) – кількість відрізків у магічному наборі. Далі йде N + 1 рядок, де рядок з номером містить два числа, L_i, R_i (1 \le L_i \le R_i \le 10^9) – кінці відповідного відрізку. Відрізки пронумеровані починаючи з 1.
У єдиний рядок вихідного файлу виведіть одне число – номер відрізку, який Леді потрібно видалити, щоб відрізки, що залишились, формували магічний набір. Якщо таких відрізків декілька, виведіть будь-який. Гарантується, що рішення існує.
Приклад 1
Приклад 2
Ця задача складається з чотирьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 13 | 1 \le N \le 500 | |
2 | 14 | 1 \le N \le 10^5; відрізок Марічки не перетинається з жодним іншим | |
3 | 21 | 1 \le N \le 10^4; 1 \le L_i \le R_i \le 100 | |
4 | 52 | 1 \le N \le 10^5 |