Valid Array Division

You are given an array \( A \) of \( n \) integers. Your task is to count the number of ways to split the array into two non-empty subarrays \( B \) and \( C \) such that the maximum element in \( B \) is strictly less than the minimum element in \( C \).

More formally, consider an index \( i \) satisfying \( 1 \leq i < n \). Let \( B = [A_0, A_1, \ldots, A_{i-1}] \) and \( C = [A_i, A_{i+1}, \ldots, A_{n-1}] \). You need to determine for how many such indices the following condition holds: \[ \max(B) < \min(C) \]

This problem allows you to use efficient preprocessing techniques with prefix maximums and suffix minimums.

inputFormat

The first line contains an integer \( n \), representing the number of elements in the array.

The second line contains \( n \) space-separated integers representing the array \( A \).

outputFormat

Output a single integer denoting the number of valid divisions.

## sample

5
1 2 3 4 5

4

</p>