Maximum Segments Ending Below Their Maximum

You are given an integer array nums of length n.

A segment is a contiguous subarray of nums. A segment is valid if its last element is strictly less than the maximum element of the segment.

Choose a set of non-overlapping valid segments (each index belongs to at most one segment; indices may be left out). Return the maximum number of valid segments that can be chosen.

Examples

Example 1

Input: nums = [2,5,1,4,3]
Output: 2
Explanation: [2, 5, 1] ends in 1 < 5 and [4, 3] ends in 3 < 4. No three disjoint valid segments exist.

Example 2

Input: nums = [4,4]
Output: 0
Explanation: [4, 4] ends in 4, which is not strictly below its maximum 4, and a single element is never below its own maximum.