题目内容

在一条编号为 $1 \sim n$ 的路径上，从位置 $i$ 可以进行如下两种移动：

• 以代价 $0$ 通过传送门移动到位置 $a_i$；
• 若 $i < n$，以代价 $1$ 向右移动到位置 $i+1$。

给定长度为 $n$ 的数组 $a$（其中 $1 \le a_i \le n$）。你从位置 $1$ 出发，目标是到达位置 $n$。每次移动产生的代价会累加，求到达位置 $n$ 的最小总代价。

输入描述

输入包含多组测试数据。第一行包含整数 $T$（$1 \le T \le 10^5$）表示测试组数。每组数据描述如下：

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

保证所有测试中 $n$ 的总和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示从位置 $1$ 到位置 $n$ 的最小总代价。

样例1

输入

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

输出

2
0
5

说明

样例一：一种最优方案为 $1 \xrightarrow{+1} 2 \xrightarrow{0} 3 \xrightarrow{+1} 4 \xrightarrow{0} 5$，总代价 $2$。 样例二：$1 \xrightarrow{0} 2 \xrightarrow{0} 3 \xrightarrow{0} 4$，总代价 $0$。 样例三：传送门均回到 $1$，只能向右前进 $5$ 次，总代价 $5$。