题目描述

给你一个 \(N\) 个整数组成的不降序列 \(a_1,a_2,…,a_n\)。回答每个询问区间 \([i,j]\) \((1<=i<=j<=n)\)最频繁出现数的次数。

格式

输入格式

输入有多组测试。

每组测试第一行两个整数 \(N\) 和 \(Q\)。

第二行，\(N\) 个整数 \(a_1\) 至 \(a_n\)，\((-10^5<=a_i<=10^5,a_i<=a_i+1)\)。

一下 \(Q\) 行，每行一个询问，由两个整数 \(i、j\)，表示区间 \([i,j]\)。

最后一组测试后面跟着一个包含单个 \(0\) 的行。

输出格式

每个询问，输出一行。表示询问区间最频繁出现数的次数。

样例1

样例输入1

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

样例输出1

1
4
3

限制

时间：\(1s\) 空间：\(64M\)

对于 \(30\%\) 的数据：\(1<=n,q<=10^2\);

对于 \(50\%\) 的数据：\(1<=n,q<=10^3\);

对于 \(100\%\) 的数据：\(1<=n,q<=10^5\);

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛 \(T3\)