p488.ans1
======================
1 3
1 0

=================
p488.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;
}

=================
p488.in1
======================
2
10
4 4 1 6 3 2 1 2 5 7
10
2 3 4 5 6 7 8 9 10 9


=================
statement.txt
======================
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

=================
