896. Find and Earn

0

Medium

Bob will receive a coin for each longest increasing subsequence he finds in an array of integers, nums.
Return the total number of coins Bob can earn.
A longest increasing subsequence is a sequence that strictly increases in value.
Note: The array must be strictly increasing for a subsequence to be considered longest.

Input Format

The first line of input contains an integer n, representing the size of the nums array.
The following n lines contain the elements of the nums array.

Output Format

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

Example

Input

5 1 3 5 4 7

Output

2

Constraints

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6
  • Loading...

    View Submissions

    Console