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.

5
1 2 2 3 3

1

4
2 1 2 1

3