488. Dales and Hills
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Let's consider a number sequence
a1, ·s,
aN. We call the continuous subsequence
ai, ·s,
aj, ·s,
ak (1 ≤
i <
j <
k ≤
N) of the sequence a
![](https://espresso.codeforces.com/54a4363c38e86b99e3d1fe40f05ea54d3df8a119.png)
if
at <
at+1 for any
i ≤
t <
j and
at >
at+1 for any
j ≤
t <
k. In this case we call
![](https://espresso.codeforces.com/9f455a29549c8b2a804908c526a5f7a64968880a.png)
the
![](https://espresso.codeforces.com/afba0dd8a79c4865ce617621de5de7ad78e781d7.png)
of the hill. Similarly, we call the continuous subsequence a
![](https://espresso.codeforces.com/0bf294cab1e242f83babb52f26b9fe790b5527a6.png)
if
at >
at+1 for any
i ≤
t <
j and
at <
at+1 for any
j ≤
t <
k. In this case we call
![](https://espresso.codeforces.com/9f455a29549c8b2a804908c526a5f7a64968880a.png)
the
![](https://espresso.codeforces.com/9dec1f986aa35e67d2c4921941fb428fa4a888a7.png)
of the dale.
Compute the height of the highest hill and the depth of the deepest dale in the given sequence.
Input
The first line of the input file contains
T (
![](https://espresso.codeforces.com/148b015b0dfc2d21b6fe5f5e863eecdd3c56279c.png)
), the number of test cases. The test cases follow, occupying two lines each. The first of the two lines contains
N (
![](https://espresso.codeforces.com/7e56210a5ea11c92400e3258ec25460ec767ccf6.png)
), the second the members of the sequence, separated by spaces. The sum of values of
N over all test cases in the file does not exceed
![](https://espresso.codeforces.com/b9d657f290f73ee58a67f0b3aaa46c2dc225f6b9.png)
. The absolute values of the members of the sequences do not exceed
![](https://espresso.codeforces.com/05674014d8110ee31d682ccf49d98e09aca1fb75.png)
.
Output
The output file should consist of
T lines and each line should contain two integers, the height of the highest hill and the depth of the deepest dale. If there are no hills or no dales, output 0 in the corresponding position.
Example(s)
sample input | sample output |
2
10
4 4 1 6 3 2 1 2 5 7
10
2 3 4 5 6 7 8 9 10 9
|
1 3
1 0
|