题目描述

此题$N$的范围增加了,如果你能通过此题就也能通过Easy版本

题目描述

你有一个长度为$N$的序列$A_{1},A_{2}...A_{N}$， 请输出

$$\max_{1\le i\le j\le N} \left \{A_{j}-A_{i} \right \} $$

就是从数组中任选两个数将它们相减(下标大的作为被减数)，所有情况的结果取最大的值

输入格式

第一行包含一个整数 $T (1≤T≤10^{4})$—测试用例的数量。
每一个测试用例有两行:
第一行一个整数$N$表示序列的长度$(1 \le N \le 10^{3})$
第二行$N$个整数$N$表示序列的元素 $A_{1},A_{2}...A_{N}$$(1 \le A_{i} \le 10^{6})$

输出格式

输出共$T$行
每一行输出的最大值

样例

2
5 
9 2 3 9 11
5 
11 10 9 8 7

9
0

解释：
第一个样例的最大值取的是$i=2,j=5$

$$A_{j}-A_{i}=11-2=9$$

第二个样例的最大值为$0$，取$i=j$最优， 因为$i<j,A_{i}>A_{j}$，计算的为负值