Responsive image

问题 2424 --最大进步

2424: 最大进步

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

你进行了 n 次考试,第 i 次考试的分数是 ai。

你想知道你最大进步的幅度是多少,定义最大进步的幅度为:

1. 选定一段 极长 的区间 [l,r]满足 al≤al+1≤⋯≤ar。

2. 满足条件一的情况下,使得 ar−al 的值最大。

如果你有多段最大进步,你需要输出所有的最大进步段,每一段用两个数 l,r 表示,按照区间的左端点升序输出。

一句话题意:找到所有极长的不严格上升段,并找出它们当中右端点权值 - 左端点权值最大的那些个段,输出端点坐标。

输入描述

第一行输入一个正整数T(1<=T<=1e5),表示数据组数。
每组数据第一行输入一个正整数n(2<=n<=1e5) 。

输出描述

对每组询问输出一行,表示你所得到的所有答案。

样例输入

1
7
1 3 5 2 4 6 3

样例输出

1 3 4 6

提示

区间 [1,3] 是 1,3,5满足 1≤3≤5 并且 5−1=4 差值最大。

区间 [4,6] 同理,6−2=4 同样为最大的差值。


来源

[提交][状态]
ACM算法攻关部