A drilling rig pulls n core samples from a mineshaft, recording each sample's density in the order it was extracted (top of the shaft first). A sinking run is any subsequence of samples (not necessarily adjacent) read in extraction order whose densities are strictly decreasing. Report the greatest number of samples a sinking run can contain.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the densities in extraction order.
Output format
A single integer: the length of the longest strictly decreasing subsequence.
Constraints
- 1 <= n <= 100000
- -1000000000 <= density <= 1000000000