如何在$1 \sim n$的序列(不保证顺序递增或递减）中$m$次询问的一个区间中$[l,r]$中求得最大值和次大值

已知可以用分治的思想，但本人蒟蒻，不会线段树，也无法处理$n$与$m$的庞大数据($n,m \le 200000$)遂求助(现在已经有人开始讲了，但我想知道有没有不用线段树的方法)

例子

输入
第一行$n,m$
第二行这个序列
接下来$m$行表示一个区间$[l,r]$ 求最大值和次大值

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

输出
第一个最大值，第二个次大值

5 3
5 4
5 1
4 2
5 3