Реалізуйте структуру даних для ефективного обчислення номера лівого максимального з кількох елементів масиву, що йдуть поспіль.

Формат вхідних даних

У першому рядку вводиться одне натуральне число \(N\) \((1 ≤ N ≤ 100000)\) — кількість чисел у масиві.

У другому рядку вводяться \(N\) чисел від 1 до 100 000 - елементи масиву.

У третьому рядку вводиться одне натуральне число \(K\) \((1 ≤ K ≤ 30000)\) — кількість запитів на обчислення максимуму.

У наступних K рядках вводиться по два числа номери лівого та правого елементів відрізка масиву (вважається, що елементи масиву нумеруються з одиниці).

Формат вихідних даних

Для кожного запиту виведіть індекс максимального елемента на вказаному відрізку масиву. Якщо максимальних елементів кілька, виведіть номер найлівішого з них.

Числа виводьте в один рядок через пробіл.

Приклад вхідних даних

5
2 2 2 1 5
2
2 3
2 5

Приклад вихідних даних

2 5