题目背景

体检报告上的指标值经常出现重复：一个人可能连续几次测量都落在同一个数值上。医生既要看区间内的最高值，也要知道这个最高值有多"站得住脚"。

题目描述

给定长度为 $n$ 的整数序列 $a$ 和 $m$ 次询问。每次询问给出 $l,r$，请你回答区间 $a_l,a_{l+1},\dots,a_r$ 中的最大值，以及该最大值在区间内出现的次数。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行两个整数 $l,r$。

输出格式

对每次询问输出一行两个整数：区间最大值以及它在该区间内出现的次数。

输入输出样例 #1

输入 #1

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

输出 #1

3 2
3 3
3 1

说明

样例解释

区间 $[1,4]$ 内的值为 $1,3,3,2$，最大值 $3$ 出现 $2$ 次；区间 $[2,6]$ 内最大值 $3$ 出现 $3$ 次；区间 $[5,5]$ 只有一个元素。

数据范围

• 对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^5$，$|a_i|\le 10^9$，$1\le l\le r\le n$。