题目描述

已知一只股票未来N天每天的价格。可以依次完成两次交易，每次交易先买入再卖出，利润等于卖出价格减去买入价格。第一次卖出之后才能第二次买入。

同一天可以完成多次买卖，因此也可以用同一天买入和卖出表示一次利润为0的交易。求总利润的最大值。

输入格式

第一行一个整数T。每组数据先输入一个整数N，再输入N个整数，表示按日期顺序给出的价格。

输出格式

每组数据输出一行，表示最大总利润。

样例

3
7
5 14 -2 4 9 3 17
6
6 8 7 4 1 -2
4
18 9 5 2

28
2
0

数据范围

1≤T≤50，1≤N≤100000；每天的价格是绝对值不超过1000000的整数，可以为负数。