题目描述

Aki 有一个长度为 n 的序列 $a_1, a_2, ..., a_n$，其中每个元素 $a_i$ 都是 1 到 n 之间的整数，不要求互不相同。

对于一个非空子区间 [l, r]，定义它的 凝聚力 为：

$(区间最大值 - 区间最小值 + 1) - 区间长度$

也就是：

$(max(a[l..r]) - min(a[l..r]) + 1) - (r - l + 1)$

Aki 想知道，在所有非空子区间中，最大的凝聚力是多少。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 T，表示数据组数。

对于每组数据：

• 第一行输入一个整数 n
• 第二行输入 n 个整数 $a_1, a_2, ..., a_n$

额外保证单个测试文件中所有数据组的 n 之和不超过 $2\times10^5$。

输出格式

对于每组数据，输出一行一个整数，表示最大的凝聚力。

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

3
0