Магiчний набiр#166

Магiчний набiр

1 second
512 megabytes
Medium

Леді дуже довго відкладала кошти на те, щоб купити собі магічний набір відрізків. Набір називається магічним, якщо у наборі рівно відрізків та кожна пара відрізків має спільну точку.

Коли вона назбирала необхідну суму та купила набір, відразу ж вирішила пограти з ним. Це було просто неймовірно! Але сталося те, чого вона ніяк не могла передбачити: коли вона пішла їсти, її маленька сестра Марічка підкинула туди ще один відрізок та перемішала набір, то ж Леді не знає, який саме відрізок підкинула Марічка. Вона дуже розізлилася на сестру, але що поробиш – доведеться видалити з набору один відрізок, щоб той знову став магічним.

Вам, як найкращому програмісту в світі, Леді пропонує написати програму, яка за заданим числом та відрізками, що лежать перед нею, визначить, який саме відрізок треба видалити.

Input

У першому рядку задається єдине число (1 \le N \le 10^5) – кількість відрізків у магічному наборі. Далі йде N + 1 рядок, де рядок з номером містить два числа, L_i, R_i (1 \le L_i \le R_i \le 10^9) – кінці відповідного відрізку. Відрізки пронумеровані починаючи з 1.

Output

У єдиний рядок вихідного файлу виведіть одне число – номер відрізку, який Леді потрібно видалити, щоб відрізки, що залишились, формували магічний набір. Якщо таких відрізків декілька, виведіть будь-який. Гарантується, що рішення існує.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

Ця задача складається з чотирьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.

№ підзадачі

Бали

Обмеження

Примітка

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