题目描述

给定 \(n + 1\) 天的股票价格序列 \(A_1, A_2, \dots, A_{n + 1}\)，其中 \(1 \le A_i \le 10^9\)。小 A 初始时刻没有持有任何股票，且拥有足够多现金。

在第 \(i\) （\(1 \le i \le n\)）天，小 A 必须且只能进行一次操作，操作有且仅有以下两种：

• Buy：支付 \(A_i\) 元，买入 \(1\) 股股票；
• Sell：卖出 \(1\) 股股票，获得 \(A_i\) 元。

需要满足以下约束：

• 任何时刻，小 A 持有的股票数量都不能为负数；
• 如果当天选择卖出，那么在卖出前手中必须至少持有 \(1\) 股股票。
• 浮盈加仓：小 A 是狂热的短线战士，假设现在是第 \(i\) （\(3 \le i \le n\)）天，如果最近连续的两笔交易（\(i - 2\), \(i - 1\)）都是购买且价格不降 \(A_{i - 1} \ge A_{i - 2}\)，小 A 会在第 \(i\) 天果断选择购买。

第 \(n\) 天结束后，第 \(n + 1\) 天小 A 会以当天价格无条件卖出所有手上的股票（如果有），计算 小 A 能够获得的最大净收益是多少。

输入格式

第一行包含一个整数 \(T\)，表示数据组数。

接下来每组数据包含两行：

• 第一行一个整数 \(n\)，表示前 \(n\) 天可以进行交易；
• 第二行包含 \(n + 1\) 个整数 \(A_1, A_2, \dots, A_{n + 1}\)，其中 \(A_i\) 表示第 \(i\) 天的交易价格。

数据范围满足： \(T = 5\)， \(1 \le n \le 500\)，且所有测试点中 \(\sum n \le 2000\)。

输出格式

对于每组数据，输出一行，一个整数，表示在第 \(n + 1\) 天结束后小 A 能够获得的最大净收益。

样例输入

1
4
1 3 2 4 5

样例输出

10