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

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

У першому рядку вводиться одне натуральне число \(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 2
5 1