A tournament leaderboard log lists n scores in the order they were posted. A climb line is a subsequence of posts (not necessarily adjacent), in posted order, whose scores are strictly increasing. Among all climb lines, consider only the longest ones (those achieving the maximum possible length). Report how many such longest climb lines exist. Two climb lines are considered different if they use different sets of positions, even if the score values match.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the scores in posted order.
Output format
A single integer: the number of longest strictly increasing subsequences.
Constraints
- 1 <= n <= 2000
- -1000000000 <= score <= 1000000000
- The answer fits in a signed 64-bit integer.