题目描述

Polycarp 在玩一个新的电脑游戏，游戏中有 $n$ 个连续的石头，摧毁位于 $i$ 处的石头需要 $a_i$ 的力量，摧毁每块石头需要的力量都不同。

在每回合中，Polycarp 可以摧毁最左边或最右边的石头，他现在想摧毁所需力量最小和最大的两块石头（即摧毁 $a_i$ 最小和最大的石头）。

输入格式

在输入的第一行为一个整数 $t$（$1 \le t \le 100$），为数据组数。

接下来对于每组数据，第一行为一个整数 $n$（$2 \le n \le 100$），为石头的数量；第二行有 $n$ 个彼此不同的整数 $a_1,a_2, \ldots ,a_n$（$1\leq a_i\leq n$），为摧毁每块石头所需的力量。

输出格式

对于每组数据，输出一个整数表示摧毁 $a_i$ 最小和最大的这两块石头所需的最小操作次数。

样例

5
5
1 5 4 3 2
8
2 1 3 4 5 6 8 7
8
4 2 3 1 8 6 7 5
4
3 4 2 1
4
2 3 1 4

2
4
5
3
2