小柒的颜色
题号：NC288869
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小柒最近获得了一个由 n 个元素组成的数组，数组的第 i 个元素有一个颜色编号 a_i。
\hspace{15pt}对于第 i 个元素和第 j 个元素满足 1 \le i \lt j \le n，如果他们的颜色相同（即 a_i=a_j），那么这两个元素会产生 a_i 点能量。
\hspace{15pt}小柒是一个好奇的学生，他一共会进行 q 次询问，每次询问给定一个区间 (l,r) \left(1 \leq l \leq r \leq n\right)，他想要知道在这段区间内会产生多少能量，以及产生能量最多的颜色是哪个颜色。如果有多个颜色的能量相同，那么告诉他颜色编号最小的那个颜色。

输入描述:

\hspace{15pt}第一行输入两个整数 n,q\left(1 \leq n,q \leq 10^5\right) 代表数组中的元素个数、询问次数。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1 \leq a_i \leq n\right) 代表每个位置的颜色编号。 
\hspace{15pt}此后 q 行，每行输入两个整数 l,r\left(1 \leq l \leq r \leq n\right) 代表一次询问。

输出描述:

\hspace{15pt}对于每次询问，新起一行。输出两个整数，第一个整数代表该区间内产生的能量总和，第二个整数代表产生能量最多的最小颜色编号。
示例1

输入

复制 
8 5
1 3 4 1 5 5 1 3
1 8
1 4
4 8
5 6
2 2

输出

复制 
11 5
1 1
6 5
5 5
0 3