题目背景

小苯有一个长度为 $n$ 的序列，他定义了序列子区间的“凝聚力”，现在他想知道所有非空子区间中最大的凝聚力是多少。

题目描述

小苯有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，其中每个元素 $a_i$ 是 $1$ 到 $n$ 之间的整数（不一定互不相同）。

他定义序列的一个子区间的凝聚力为：该子区间中所有元素的值域长度（最大值减最小值加 $1$）减去子区间长度。

形式化地说，对于子区间 $a_l, a_{l+1}, \dots, a_r$（$1 \le l \le r \le n$），记 $M = \max\{a_l, a_{l+1}, \dots, a_r\}$，$m = \min\{a_l, a_{l+1}, \dots, a_r\}$，则其凝聚力为：

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

输入格式

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

第一行输入一个整数 $T$（$1 \le T \le 10^4$），代表数据组数。

对于每组测试数据：

• 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$）。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

保证单个测试文件的所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

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

样例输入 #1

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

样例输出 #1

0
3

说明/提示

样例 1 解释

对于第一组测试数据，所有子区间的凝聚力均为 $0$：

• 子区间 $[1,1]$ 的凝聚力为 $(1-1+1)-1=0$；
• 子区间 $[1,2]$ 的凝聚力为 $(2-1+1)-2=0$；
• 子区间 $[1,3]$ 的凝聚力为 $(3-1+1)-3=0$；
• $\dots$

以此类推，最大凝聚力为 $0$。

数据范围与约定

• 对于 $100\%$ 的数据：
  • $1 \le T \le 10^4$
  • $1 \le n \le 2 \times 10^5$
  • $1 \le a_i \le n$
  • 单个测试文件中 $\sum n \le 2 \times 10^5$