LMIS - Longest Monotonically Nondecreasing Sequence

You are given a set of numbers on the standard input. You need to figure out what is the smallest number of them that you need to remove so that you are left with the Longest Monotonically Nondecreasing Sequence.

Input

On the standard input your are given a set with less than 1000000 integers each less than 30000.

Output

A single integer - the number of numbers you will remove.

Example

Input:
3 1 2 0 5 4 10

Output:
3
(you need to remove 3, 0, (5 or 4), then you will be left with 1, 2, (5 or 4), 10).

Added by:Nikola P Borisov
Date:2008-11-09
Time limit:8.729s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2021-06-02 21:40:57
I am getting the wrong answer to this problem,
can anyone tell me what might I be missing in this question.
I am pretty sure I implemented this problem in right way
2020-05-13 12:57:00
how to take input for this problem? Please help.
2010-02-19 13:10:37 FooBar
After solving, it doesn't show up in the list of solved problems (same issue as Kunal Jain's). What's up with this?

Last edit: 2010-02-19 13:10:54
2009-03-08 14:33:07 [Trichromatic] XilinX
It has been moved to tutorial problem set.
2009-03-08 12:39:31 Kunal Jain
i got accepted but now it is not showing that it has been solved..
2009-03-06 20:18:54 ~!(*(@*!@^&
if input is 1 1 1 1 : so the number is 1 or 3? (I guess 1)


2009-03-06 19:35:24 Paul Draper
All integers >= 0?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.