跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#T261101I. 胆子肥嘟嘟,闪现也收费

胆子肥嘟嘟,闪现也收费

袋鼠嫌送餐路线太长,现场展示了自己的“闪现送达”。

它刚侧过头准备说一句“胆子真是肥嘟嘟的”,图灵娘已经递来账单。袋鼠的耳朵一点点垂了下来:“那我正常往前走,总不用也收费吧?”

往前走确实免费,传送可就另算了。

本题场景插图

任务说明

有 nn 个格子,初始计数全为0。第一回合,袋鼠必须放在第1格,该格计数加一,这次放置不算传送。此后每回合选择一种动作:

  • 向右移动一格(最后一格不能这样移动),不增加传送次数;
  • 传送到任意格子,包括当前格,传送次数加一。

每次动作结束,所在格计数加一。求使各格计数恰好等于 c1,…,cnc_1,\ldots,c_n 所需的最少传送次数。

输入格式

第一行输入测试组数 tt。每组先输入 nn,再输入 nn 个整数 cic_i。

输出格式

每组输出一个整数,表示最少传送次数。

数据范围与计分

1≤t≤1041\le t\le10^4,1≤n≤2×1051\le n\le2\times10^5,0≤ci≤1090\le c_i\le10^9,c1≥1c_1\ge1;单文件所有 nn 之和不超过 2×1052\times10^5。

样例 1

3
4
2 0 3 1
1
1
1
4
4
0
3

说明

故事与对话为本次校园考核二创。插图仅用于展示情境;全部解题规则均已在文字中给出。