<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

88. 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  if at < at+1 for any i ≤ t < j and at > at+1 for any j ≤ t < k. In this case we call  the  of the hill. Similarly, we call the continuous subsequence a  if at > at+1 for any i ≤ t < j and at < at+1 for any j ≤ t < k. In this case we call  the  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 (), the number of test cases. The test cases follow, occupying two lines each. The first of the two lines contains N (), 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 . The absolute values of the members of the sequences do not exceed .

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

<|response|>
1. Abridged Problem Statement  
Given an integer sequence a₁…aₙ, a “hill” is any contiguous subsequence that strictly increases then strictly decreases (both parts non-empty). Its height = min(length of increasing part, length of decreasing part). A “dale” is strictly decreasing then strictly increasing; its depth is defined analogously. For each test case, report the maximum hill height and the maximum dale depth (0 if none exist).

2. Key Observations  
- Every hill or dale has a single “peak” or “valley” at some index i.  
- To know how far an increasing run extends into i from the left, and how far a decreasing run extends out of i to the right (and vice versa), we can precompute run lengths.  
- We only need four arrays of size n:  
  • up_left[i]: length of strict increase ending at i  
  • down_left[i]: length of strict decrease ending at i  
  • up_right[i]: length of strict increase starting at i  
  • down_right[i]: length of strict decrease starting at i  
- Once these are known, for each i:  
  • If up_left[i]>0 and down_right[i]>0, there is a hill centered at i of height = min(up_left[i], down_right[i]).  
  • If down_left[i]>0 and up_right[i]>0, there is a dale centered at i of depth = min(down_left[i], up_right[i]).  
- Scan i from 0 to n−1, track the maximum hill height and dale depth. Total time O(n) per test.

3. Full Solution Approach  
1. Read n and array a[0…n−1].  
2. Initialize four arrays of size n to zero.  
3. Forward pass i=1…n−1:  
   - if a[i]>a[i−1], up_left[i]=up_left[i−1]+1  
   - if a[i]<a[i−1], down_left[i]=down_left[i−1]+1  
4. Backward pass i=n−2…0:  
   - if a[i]>a[i+1], up_right[i]=up_right[i+1]+1  
   - if a[i]<a[i+1], down_right[i]=down_right[i+1]+1  
5. Initialize max_hill=0, max_dale=0.  
6. For i in [0…n−1]:  
   - If up_left[i]>0 and down_right[i]>0: max_hill = max(max_hill, min(up_left[i], down_right[i]))  
   - If down_left[i]>0 and up_right[i]>0: max_dale = max(max_dale, min(down_left[i], up_right[i]))  
7. Output max_hill and max_dale.

4. C++ Implementation with Detailed Comments  

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // Arrays to hold run lengths
        vector<int> up_left(n, 0), down_left(n, 0);
        vector<int> up_right(n, 0), down_right(n, 0);

        // Forward pass: compute runs ending at i
        for (int i = 1; i < n; i++) {
            if (a[i] > a[i - 1]) {
                // increasing step
                up_left[i] = up_left[i - 1] + 1;
            }
            if (a[i] < a[i - 1]) {
                // decreasing step
                down_left[i] = down_left[i - 1] + 1;
            }
        }

        // Backward pass: compute runs starting at i
        for (int i = n - 2; i >= 0; i--) {
            if (a[i] > a[i + 1]) {
                // a[i] -> a[i+1] is decreasing, so run of decrease to the right
                up_right[i] = up_right[i + 1] + 1;
            }
            if (a[i] < a[i + 1]) {
                // a[i] -> a[i+1] is increasing
                down_right[i] = down_right[i + 1] + 1;
            }
        }

        int max_hill = 0, max_dale = 0;

        // Evaluate each index as center of hill or dale
        for (int i = 0; i < n; i++) {
            // Hill: strictly increase into i, strictly decrease out of i
            if (up_left[i] > 0 && down_right[i] > 0) {
                int height = min(up_left[i], down_right[i]);
                max_hill = max(max_hill, height);
            }
            // Dale: strictly decrease into i, strictly increase out of i
            if (down_left[i] > 0 && up_right[i] > 0) {
                int depth = min(down_left[i], up_right[i]);
                max_dale = max(max_dale, depth);
            }
        }

        // Output result for this test
        cout << max_hill << " " << max_dale << "\n";
    }

    return 0;
}

5. Python Implementation with Detailed Comments  

```python
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    # Prepare arrays for run lengths
    up_left = [0] * n
    down_left = [0] * n
    up_right = [0] * n
    down_right = [0] * n

    # Forward pass: runs ending at i
    for i in range(1, n):
        if a[i] > a[i - 1]:
            up_left[i] = up_left[i - 1] + 1
        if a[i] < a[i - 1]:
            down_left[i] = down_left[i - 1] + 1

    # Backward pass: runs starting at i
    for i in range(n - 2, -1, -1):
        if a[i] > a[i + 1]:
            up_right[i] = up_right[i + 1] + 1
        if a[i] < a[i + 1]:
            down_right[i] = down_right[i + 1] + 1

    max_hill = 0
    max_dale = 0

    # Check each position as a potential center
    for i in range(n):
        # Hill condition
        if up_left[i] > 0 and down_right[i] > 0:
            height = min(up_left[i], down_right[i])
            if height > max_hill:
                max_hill = height
        # Dale condition
        if down_left[i] > 0 and up_right[i] > 0:
            depth = min(down_left[i], up_right[i])
            if depth > max_dale:
                max_dale = depth

    # Print the results
    print(max_hill, max_dale)

def main():
    T = int(input())
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()
```