XX大学的金字塔

Time Limit
1s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
6.67%(2/30)
Description:

众所周知，在很久以前， XX 大学3号教学楼的地下有一个神奇的金字塔，这是很久以前有智慧的巨龙们的杰作。如图，金字塔的顶层只有一个房间，每向下一层便多一个房间，房间的位置还展示了住在里面的巨龙们之间的主仆关系：住在某房间的巨龙，是住在这个房间正下方两个房间巨龙的主人。即，住在第i层第j号位置的巨龙，是住在第i+1层第j号和第j+1号位置巨龙的主人。

作为巨龙，他们当然十分热爱珠宝，而作为生活在中华大地上的巨龙，他们还有一套严格的等级进贡体制：每个房间的巨龙会收到其两个仆人价值分别为x和y的的贡品，而这个巨龙还需要向他的主人进贡进价值为max(x, y)的贡品，同时，这个值也代表着这条龙的开心度。特别的，住在金字塔顶端的巨龙不需要向任何龙进贡；驻守在金字塔边缘两列的巨龙只需要向自己唯一的主人进贡。
现已知住在金字塔顶第n层每个巨龙的开心度，求住在金字塔第n层及以上每条巨龙的开心度之和

Input:

输入包含多组测试数据，第一行为一个正整数 T (1 ≤ T ≤ 10) 表示有 T 组测试数据。
测试数据第一行包含一个正整数 n (1 ≤ n ≤ 106)；
第二行包含 n 个非负整数，ai 依次表示住在第 n 层第 i 条巨龙的开心度

Output:

对于每组测试数据，
输出一行包含一个非负整数 Ans 表示问题答案。

Sample Input:
2
4
3 1 2 4
5
2 3 1 4 2
Sample Output:
30
49
Source:

Davones

Submit