题目描述

现有由 $n$ 块小积木拼成的一个长条积木，从左到右的小积木编号依次为 $1..n$，其中第 $i$ 块小积木的颜色为 $c_i$。

小爱现在有 $q$ 个问题，第$i$个问题会包含两个参数 $l_i,r_i$ ，请你帮忙回答，此时可以对所有积木重新染色，在保证若原状态下两块积木颜色相同、染色后两块积木颜色仍保持相同；原状态下两块积木颜色不同、染色后两块积木颜色仍保持不同的情况下，如何染色才能使得染色后，第$l_i$到$r_i$块积木的颜色编号之和最小？

输入格式

输入第一行，两个正整数 $n,q$ 第二行，$n$个正整数 $c_1,c_2,...,c_n$表示积木初始状态下颜色 接下来 $q$ 行，每行两个正整数 $l_i,r_i$。

输出格式

输出共 $q$ 行，第 $i$ 行表示第 $i$ 个问题的答案。

6 2
1 1 3 2 3 1 
1 3
3 6

4
7

样例解释 1

对于第1问：1颜色不变，把3染成2，得到[1,1,2]，和为4 对于第2问：把3染成1，把1染成3，2不变，得到[1,2,1,3]，和为7

数据范围

• 对于 $30\%$的数据，$1 \leq n \leq 100$
• 对于 $60\%$的数据，$1 \leq n \leq 10^3$
• 对于 $100\%$的数据，$1 \leq n \leq 10^5,1 \leq q \leq 10^5,1 \leq l_i\leq r_i \leq n,1 \leq c_i \leq 10^9$