## 1. Abridged Problem Statement

Given an integer sequence a₁…aₙ, a "hill" is a contiguous subsequence that strictly increases then strictly decreases (each part at least length 1). Its height is the minimum of the up-run and down-run lengths. A "dale" is strictly decreasing then strictly increasing, and its depth is likewise the minimum of the down- and up-run lengths. For each test case, output the maximum hill height and the maximum dale depth (0 if none exist).

## 2. Detailed Editorial

### Overview

We need to scan the sequence and detect for every potential "peak" or "valley" how long the increasing/decreasing runs extend to the left and right. Then for each center we can compute the hill height or dale depth in O(1) and take the maximum.

### Definitions

- `up_left[i]` = length of the strictly increasing run ending at i (counting steps to the left of i).
- `down_left[i]` = length of the strictly decreasing run ending at i (counting steps to the left of i).
- `up_right[i]` = length of the strictly decreasing run starting at i going right (i.e. a[i] > a[i+1] > ...).
- `down_right[i]` = length of the strictly increasing run starting at i going right (i.e. a[i] < a[i+1] < ...).

Note: `up_right` tracks the downhill slope to the right of a peak (the "down" side of a hill), and `down_right` tracks the uphill slope to the right of a valley (the "up" side of a dale). The naming follows the run arrays in the code.

### Computation

1. Forward pass from i=1 to n−1:
   - If a[i] > a[i−1], `up_left[i] = up_left[i−1] + 1`, else 0.
   - If a[i] < a[i−1], `down_left[i] = down_left[i−1] + 1`, else 0.
2. Backward pass from i=n−2 down to 0:
   - If a[i] > a[i+1], `up_right[i] = up_right[i+1] + 1`, else 0.
   - If a[i] < a[i+1], `down_right[i] = down_right[i+1] + 1`, else 0.
3. For each i:
   - If `up_left[i] > 0` and `up_right[i] > 0`, candidate hill height = `min(up_left[i], up_right[i])`. Track max.
   - If `down_left[i] > 0` and `down_right[i] > 0`, candidate dale depth = `min(down_left[i], down_right[i])`. Track max.

Time complexity per test: O(n). Memory O(n).

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // For every index compute the length of the strictly increasing run ending
    // there from the left (up_left) and starting there to the right (up_right),
    // and symmetrically the strictly decreasing runs (down_left, down_right).
    // A hill peaks at i when both up_left[i] and up_right[i] are positive, and
    // its half-length is min(up_left[i], up_right[i]); a dale bottoms at i when
    // both down runs are positive. We report the maximum hill height and the
    // maximum dale depth over all indices.

    vector<int> up_left(n, 0), up_right(n, 0);
    vector<int> down_left(n, 0), down_right(n, 0);

    for(int i = 1; i < n; i++) {
        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;
        }
    }

    for(int i = n - 2; i >= 0; i--) {
        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;
        }
    }

    int max_hill = 0, max_dale = 0;

    for(int i = 0; i < n; i++) {
        if(up_left[i] > 0 && up_right[i] > 0) {
            max_hill = max(max_hill, min(up_left[i], up_right[i]));
        }

        if(down_left[i] > 0 && down_right[i] > 0) {
            max_dale = max(max_dale, min(down_left[i], down_right[i]));
        }
    }

    cout << max_hill << ' ' << max_dale << '\n';
}

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

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

## 4. Python Solution

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

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

    # Initialize run-length arrays
    up_left = [0]*n
    down_left = [0]*n
    up_right = [0]*n
    down_right = [0]*n

    # Forward pass: build left runs
    for i in range(1, n):
        if a[i] > a[i-1]:
            up_left[i] = up_left[i-1] + 1
        # else stays 0
        if a[i] < a[i-1]:
            down_left[i] = down_left[i-1] + 1
        # else stays 0

    # Backward pass: build right runs
    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 index for hills and dales
    for i in range(n):
        # Hill condition: increasing into i, decreasing out of i
        if up_left[i] > 0 and up_right[i] > 0:
            height = min(up_left[i], up_right[i])
            if height > max_hill:
                max_hill = height
        # Dale condition: decreasing into i, increasing out of i
        if down_left[i] > 0 and down_right[i] > 0:
            depth = min(down_left[i], down_right[i])
            if depth > max_dale:
                max_dale = depth

    print(max_hill, max_dale)

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

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

## 5. Compressed Editorial

- Precompute, for each index i, the length of the maximal strictly increasing run ending at i from the left (`up_left`) and the maximal strictly decreasing run starting at i going right (`up_right`), and their symmetric counterparts for decreasing/increasing (`down_left`, `down_right`), all in O(n).
- A hill peaks at i when `up_left[i] > 0` and `up_right[i] > 0`; its height = `min(up_left[i], up_right[i])`.
- A dale bottoms at i when `down_left[i] > 0` and `down_right[i] > 0`; its depth = `min(down_left[i], down_right[i])`.
- Answer is the maximum hill height and maximum dale depth. Time O(n) per test.
