An entry queue scans n badges in arrival order, each with an integer priority. A non-falling run is a subsequence of badges (not necessarily adjacent), in arrival order, whose priorities never decrease (each chosen priority is greater than or equal to the previous chosen one). Among all non-falling runs, consider only the longest ones. Report how many longest non-falling runs exist. Two runs are different if they use different sets of positions, even when the priority values coincide.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the priorities in arrival order.
Output format
A single integer: the number of longest non-decreasing subsequences.
Constraints
- 1 <= n <= 2000
- -1000000000 <= priority <= 1000000000
- The answer fits in a signed 64-bit integer.