题目描述

在Berland，反对派打算在林荫大道上举行大规模行走活动。林荫大道由 $n$ 块砖铺成，这些砖铺成一排，编号从右到左，从 $1\sim n$。反对派应该从第 $1$ 块砖开始行走，最终到达第 $n$ 块砖。在行走过程中，允许在一排砖之间从右到左移动，并且可以跳过一块砖。更正式地说，如果你站在第 $i$ 块砖 $(i < n - 1)$ 上，你可以到达第$i + 1$ 块砖或第 $i + 2$ 块砖（如果你站在第 $n - 1$ 块砖上，你只能到达第 $n$ 块砖）。我们可以假设所有反对派的行动是瞬间完成的。

为了阻止反对派的集会，Berland 血腥政权组织了雨。林荫大道上的砖质量很差，在雨中很快就会被破坏。我们知道第 $i$ 块砖在经过 $a_i$ 天的雨后被破坏（在第 $a_i$ 天，砖还没有被破坏，在第 $a_i + 1$ 天，它已经被破坏）。当然，不允许在被破坏的砖上行走！因此，如果第 $1$ 块砖被破坏，或者第 $n$ 块砖被破坏，或者在未被破坏的砖上无法从第 $1$ 块砖到达第 $n$ 块砖，那么反对派的行走被认为是受阻的。

反对派希望能够吸引更多支持者参加他们的行走活动。因此，他们有更多时间准备，就越好。帮助反对派计算他们还有多少时间，并告诉我们从第 $1$ 块砖到第 $n$ 块砖的行走还可以持续多少天。

输入

$T(T≤ 10)$ 组测试数据，每组数据格式如下：

第一行包含整数 $n（1 ≤ n ≤ 10^3）$— 林荫大道的长度（以砖块数表示）。

第二行包含 $n$ 个空格分隔的整数 $a_i$ — 表示第i块砖在 $1 ≤ a_i ≤ 10^3$ 天后被破坏。

输出

每组数据输出一行，一个数字 — 所求的天数。

4
10 3 5 10
5
10 2 8 3 5

5
5

在第一个示例中，第二块砖在第三天被破坏，唯一剩下的路径是1 → 3 → 4。在第五天，第一块砖和最后一块砖之间有两块砖的间隔，无法跳过。

在第二个示例中，路径1 → 3 → 5在第五天仍然可行。第六天，最后一块砖被破坏，行走被阻止。

Walking in the Rain CodeForces - 192B