Вам дано масив ~a~ з ~n~ елементів та ~m~ - кількість запитів, що складаються з двох чисел ~l~ і ~r~, виведіть максимальний елемент і його кількість в масиві ~a~ на відрізку від ~l~ до ~r~.

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

У першому рядку міститься число ~n~ - довжина масиву ~(1 ≤ n ≤ 10^5)~.

У другому рядку міститься ~n~ чисел ~a[i]~ - елементи масиву ~(-10^9 ≤ a[i] ≤ 10^9 )~.

У наступному рядку міститься число ~m~ - кількість запитів ~(1 ≤ m ≤ 10^5 )~.

В останніх ~m~ рядках міститися запити ~l, r~ ~(1 ≤ l, r ≤ n)~.

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

Для кожного запиту виведіть 2 числа в новому рядку.

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

5
3 2 1 2 3
3
1 3
2 4
1 5

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

3 1
2 2
3 2