题目描述

炖大鹅是鞍山当地非常受欢迎的美食，外地游客常常要排队品尝。现在有 $N$ 名游客在饭店门口拿号排队，排队位置相邻的同伴亲友可以拿一个号同时进入。饭店老板想知道，排队编号在区间 $[L_i,R_i]$ 的游客中，需要准备几桌炖大鹅？

输入格式

• 第一行两个正整数 $N$ 和 $Q$；
• 第二行 $N$ 个正整数，分别代表游客的人数；
• 接下来 $Q$ 行，每行两个正整数 $L$ 和 $R$，代表一个区间。

输出格式

共 $Q$ 行，每行一个正整数，第 $i$ 行答案表示在选定的第 $i$ 个区间中，需要安排的桌数。

样例

样例 1 输入

8 3
4 3 3 2 2 2 4 1
1 2
3 5
3 8

样例 1 输出

2
2
4

数据范围与提示

• 10% 的数据，$r_i - l_i \le 3$；
• 另外 30% 的数据，$1 \le n, Q \le 5000$；
• 对于 100% 的数据，$1 \le n, Q \le 2 \times 10^5$，$1 \le a_i \le 10^6$，$1 \le l_i \le r_i \le n$。