### 问题描述 $after$ 发现自己越来越重了，于是他决定开始他的运动计划。 他决定先从最简单的走路开始锻炼。但是，要知道， $after$ 是一个没有毅力的人，他的走路计划只坚持了 $n$ 天就停止了。于是他的朋友 $Scintilla$ 连续对他提出了 $q$ 个问题。 $after$ 觉得回答这么多问题太麻烦了，就想请你帮他回答这些问题。 ### 输入格式 第一行两个正整数 $n, q$ 。 第二行 $n$ 个正整数，第 $i$ 个为 $a_i$ 。 接下来 $q$ 行，每行 $2$ 个正整数 $l, r$ 。 ### 输出格式 $q$ 行，每行一个整数，$l ～ r$ 天一共走的路程。 ### 输入样例 ``` 2 2 2 3 1 1 1 2 ``` ### 输出样例 ``` 2 5 ``` ### 数据范围 对于 $20$% 的数据，$n \le 10^2, q \le 10^2, a_i \le 10^4$ 对于 $80$% 的数据，$n \le 10^6, q \le 10^6, a_i \le 10^3$ 对于 $100$% 的数据，$n \le 10^6, q \le 10^6, a_i \le 10^9$