A non-empty zero-indexed array A consisting of N integers is given. A pit in this aray is any triplet of integers (P, Q, R) such that:
- 0 <= P < Q < R < N;
- sequence [A[P], A[P+1], ... , A[Q]] is strictly decreasing, i.e. A[P] > A[P+1] > ... > A[Q];
- sequence A[P+1], ... , A[R] is strictly increasing, i.e. A[Q] < A[Q+1] < ... < A[R].
The depth of a pit(P, Q, R) is the number min{A[P] - A[Q], A[R] - A[Q]}.
For example, consider array A consisting of 10 elements such that:
A[0] = 0