Longest Increasing Subsequence

Cobalt Analytics tracks a sensor that reports one reading a minute. The engineers want the longest rising story they can honestly tell about a day: they may quote some readings and drop others, as long as the quoted ones keep the order the sensor produced them in and each is bigger than the one before. Two equal readings cannot both be quoted — the story has to rise, not flatten.

Task: Print how many readings the longest such rising story holds.

Input

A single line holding up to 2500 integers separated by single spaces — the readings, in the order taken. Values may repeat and may be negative. The line can be empty.

Output

One line holding a single integer: the number of readings in the longest rising story. Quoted readings need not sit next to each other, but they must keep their original left-to-right order, and each must be strictly greater than the one quoted before it. Print 0 when the line is empty.

Example:

Input:
10 9 2 5 3 7 101 18

Output:
4

(the subsequence 2, 3, 7, 18 or 2, 3, 7, 101 has length 4)