小苯的凝聚区间

题号：NC315476
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ ，其中每个元素 $a_i$ 是 $1$ 到 $n$ 之间的整数（不一定互不相同）。
$\hspace{15pt}$ 他定义序列的一个子区间的“凝聚力”为：该子区间中所有元素的值域长度（最大值减最小值加 $1$ ）减去子区间长度。
$\hspace{15pt}$ 形式化地说，对于子区间 $a_l, a_{l+1}, \dots, a_r \left(1 \leqq l \leqq r \leqq n\right)$ ，记 $M = \max\{a_l, \dots, a_r\}$ ， $m = \min\{a_l, \dots, a_r\}$ ，则其凝聚力为： $(M - m + 1) - (r - l + 1)$ 。

$\hspace{15pt}$ 小苯想知道，在所有非空子区间中，能够获得的最大凝聚力是多少。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 。
第二行输入  个整数 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示能够获得的最大凝聚力。

示例1

输入

复制

2
5
1 2 3 4 5
6
2 5 1 3 3 4

输出

复制

0
3

说明

对于第一组测试数据，所有子区间的凝聚力：
子区间  的凝聚力为 ；
子区间  的凝聚力为 ；
子区间  的凝聚力为 ；
...
以此类推，我们发现最大凝聚力为 。

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。