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

Background

Special for beginners, ^_^

Description

徐老师有一个长度为$n$的数组，想要找出数组中所有严格大于其左边相邻元素且严格大于其右边相邻元素的元素（即"山峰"元素）。对于第一个元素，只需要大于右边相邻元素；对于最后一个元素，只需要大于左边相邻元素。

请输出所有山峰元素的和。

Format

Input

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

对于每组测试，第一行一个正整数$n(1 \leq n \leq 10^5)$，表示数组长度。

第二行$n$个整数$a_i(-10^9 \leq a_i \leq 10^9)$，表示数组元素。

Output

对于每组测试，输出一个整数，表示所有山峰元素的和。

Samples

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

7
4
10

Limitation

1s, 1024KiB for each test case.