503. Find and Earn

0

Medium

Bob will receive a coin for each longest increasing subsequence he finds in an integer array nums.

If he finds additional longest increasing subsequences, he will earn more coins.

Given an integer array nums, determine the total number of coins Bob can earn.

In other words, find the number of longest increasing subsequences in the array.

If he finds additional longest increasing subsequences, he will earn more coins.

Given an integer array nums, determine the total number of coins Bob can earn.

In other words, find the number of longest increasing subsequences in the array.

**Note**that the sequence must be strictly increasing.Input Format

The first line of the input should contain an integer n, representing the size of the nums array.
Following that, there should be n lines, each containing an element of the nums array.

Output Format

Print a single integer that represents the number of coins Bob can earn.

Example

Input

5
1 3 5 4 7

Output

2

Constraints

Loading...

View Submissions

Console