该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 座城市，依次坐落在一条直线上，相邻城市之间的距离为 $1$，且相邻城市之间原本有一条公路。现在，一场百年难遇的地震导致所有公路都被破坏了。

然而，每座城市都有一台空间传送机，可以从第 $i$ 座城市传送到距离为 $a_i$ 的另一座城市，或者从距离为 $a_i$ 的城市传送到第 $i$ 座城市（即从城市 $i$ 可以传送到城市 $i + a_i$ 或 $i - a_i$，或者反向传送，如果目标城市存在的话）。

现在，政府需要开展援助工作，希望能尽快实现从任意城市到任意城市的连通性。为此，政府决定修复部分公路。问至少修复多少长度的公路，才能满足上述要求？

为了防止输入过大带来的常数问题，C++ 选手请尽量使用关闭流同步的 std::cin 和 std::cout 实现输入输出，否则可能出现因读入输出问题导致的 TLE 等。

int main(){
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  // your code

  return 0;
}

输入格式

第一行一个整数 $T$ $(1 \leq T \leq 1000)$，表示测试数据组数。

每组输入数据的第一行包含一个正整数 $n$ $(1 \leq n \leq 3 \times 10^5)$，表示城市数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq n)$，表示每个城市的传送距离。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组数据，输出一行一个整数表示需要最小需要修复公路的长度。

样例

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

0
4

限制

Time Limit: 2000ms Memory Limit: 524288KB