题目描述

一只松鼠在树林中采摘松果。假定有 \(n\) 棵树，排成一行，每棵树的高度为 \(h_i\)，每棵树的树顶上有一堆松果。

松鼠每一秒可以完成下列三个操作：

1. 向上或向下爬一个单位；
2. 采摘树顶上所有的松果；
3. 横向跳到下一棵树（注意：此时只能跳到下一棵树的同一高度）。

开始时，松鼠在第 \(1\) 棵树的根部（高度为 \(0\) 的地方）。编程计算，松鼠要采摘所有的松果，一共需要多少时间。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤100000)\)，第二行为 \(n\) 个正整数 \(h_i(≤100000)\)，分别表示每棵树的高度。

输出格式

对于每组数据，输出最短时间。

样例1

样例输入1

2
2
1 2
5
2 1 2 1 1

样例输出1

5
14

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T1\)