Вам дано масив \(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