LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDEInteractive TasksOutput-Only Tasks
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion FindSqrt Decomposition
Combinatorics
Addition PrincipleMultiplication PrincipleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsVectorsCross and Dot ProductLinesPolygonsAnglesPoint in PolygonDistances and Intersection PointsConvex HullCircles
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPDP problemsTree DPBitmask DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

Longest Increasing Subsequence II

MediumProblem #7
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

Same problem as LIS, but with constraints where the O(n²) solution is too slow. Something smarter is needed.

Given an array of numbers, find the length of the longest subsequence (the elements don't have to be next to each other) such that the numbers are strictly increasing.

This is the same task as Longest Increasing Subsequence, except only the length is required - but the array is much bigger, so the O(n2) solution will not be fast enough.

Input

First line of input will be a single number n, the length of the array.
In the next line will be n numbers a1​,a2​,…,an​.

Output

A single number - the length of the longest strictly increasing subsequence.

Example

Input
8
3 6 1 2 8 2 4 5
Output
4

The longest strictly increasing subsequence is 1,2,4,5, with a length of 4.

Constraints

1≤n≤105
1≤ai​≤109

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit