该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

半仙有很多个木棍。

描述

半仙有 $n$ 个木棍，编号分别为 $1$ 到 $n$。每次他要从编号在一定范围的木棍中取出三根木棍，使得它们的端点相连可形成三角形，但这有时不行，所以他会对它们施法，让它们的长度同时增加相同的一个非负整数，半仙让它们变长要耗体力，所以问你最少让它们增加多少可以选出满足条件的三根木棍。半仙会在问完问题后实践，木棍长度也不会在半仙问问题时发生改变，半仙不会刁难你，所以他的问题一定有解。

输入格式

• 第一行：两个正整数 $n$ 和 $q$，分别表示木棍数量与询问次数。
• 第二行：包含 $n$ 个正整数，第 $i$ 个数表示编号为 $i$ 的木棍的原始长度。
• 接下来 $q$ 行：每行两个正整数 $l$ 和 $r$，表示要从编号在 $l \sim r$ 范围内的木棍中选出三根。

输出格式

• 输出共 $q$ 行，每行一个整数，表示最少需要增加的长度。

样例

10 4
3 4 3 1 3 5 6 3 6 9
1 4
4 6
1 10
8 10

0
2
0
1

解释

1. 区间 [1, 4]：木棍长度为 [3, 4, 3, 1]，可选 3, 4, 3，无需增加即可构成三角形。
2. 区间 [4, 6]：木棍长度为 [1, 3, 5]，初始不满足三角形条件；同时增加1，也不满足条件；当所有长度加 2 后变为 [3, 5, 7]，满足条件。
3. 区间 [1, 10]：木棍长度为 [3, 4, 3, 1, 3, 5, 6, 3, 6, 9]，可直接选择 [3, 4, 3] 构成三角形。
4. 区间 [8, 10]：木棍长度为 [3, 6, 9]，增加 1 后变为 [4, 7, 10]，满足条件。

数据范围

特殊性质A：对于所有 $2\le i\le n$ 满足编号为 $i$ 的木棍比编号为 $i-1$ 的木棍长

特殊性质B：$1000\le r-l+1$

提示

本题数据较大，请用快速的输入，输出方式。