最频繁值/frequent

题目描述

$时间限制: 1 Sec \\ 内存限制: 256MB$

给定 $n$ 个整数的非递减序列 $a_1 , a_2 ,…, a_n$。对每个索引 $i$ 和 $j$ 组成的查询 $(1≤i≤j≤n)$，都确定整数 $a_i , …, a_j$ 中的最频繁值（出现次数最多的值）。

输入格式

包含多组测试用例，但是不超过 $10$ 组。每组测试用例都以两个整数 $n$ 和 $q$ 的行开始。

下一行包含 $n$ 个整数 $a_1, …, a_n$，对每个 $i ∈[1, n-1]$ 都满足 $a_i ≤a_{i+1}$。

以下 $q$ 行，每行都包含一个查询，由两个整数 $i$ 和 $j$ 组成，表示查询的边界索引。

在最后一个测试用例后跟一个包含单个 $0$ 的行。

输出格式

对每个查询，都单行输出一个整数，表示给定范围内最频繁值的出现次数。

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

1
4
3

数据范围

#1：$1≤n, q ≤10$；

#2：$1≤n, q ≤1000$；

#3：$1≤n, q ≤100000, -100000≤a_i ≤100000, i ∈[1,n]$。

备注

POJ3368