BORW - Black or White

It’s Black, It’s White, It’s Tough For You To Get By
Michael Jackson (1958-2009)


You have a sequence of integers. You can paint each of the integers black or white, or leave it unpainted. The black integers must appear in ascending order and the white integers must appear in descending order. The ascending/descending order must be strict, that is, two integers painted with the same color cannot be equal. Paint the sequence so as to minimize the number of unpainted integers.

Input

The input contains several test cases, each one described in exactly two lines. The first line contains an integer N indicating the number of elements in the sequence (1 ≤ N ≤ 200). The second line contains N integers Xi separated by single spaces, representing the sequence to paint (1 ≤ Xi ≤ 106 for 1 ≤ i ≤ N ). The last line of the input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line with an integer representing the minimum number of unpainted elements of the sequence, when the sequence is painted optimally following the rules described above.

Example

Input:
8
1 4 2 3 3 2 4 1
12
7 8 1 2 4 6 3 5 2 1 8 7
-1

Output:
0
2

Added by:Pablo Ariel Heiber
Date:2010-08-22
Time limit:9.584s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2009

hide comments
2017-05-27 02:57:14
Not very hard but interesting problem
2017-05-03 22:32:50
My first 3D-DP problem. Great Problem..!!
2017-04-23 13:29:28
nice problem . finally AC.
think about taking each element as painting white or paiting black or ignore.
make a 3D dp array and formulate recursion.
2017-04-23 13:27:46
@pandey333
i have also thought the same logic as your. But after sometime i pointed out that it was incorrect logic.
the main problem in logic that , while calculating LIS there may be a chance so that there are more than one LIS of maximum length. in that case there may be a chance for incorrectness . think again ?
2017-02-14 14:10:24
How to approach this problem???
2017-01-29 17:22:40
how can i find out the elements of LIS
2017-01-16 21:35:36 Shubham Agrawal
Can somebody give some hints for proceeding?
2016-12-10 15:01:58
case1:
find lis.
make the elements corresponding to lis as -1 in the given array;
find lds in the modified array(don't count the -1 elements).
ans1=length-(lis+lds);

case2:
find lds;
make the elements corresponding to lds as -1 in the given array;
find lis in the modified array(don't count the -1 elements).
ans2=length-(lis+lds);

final ans=max(ans1,ans2);
please comment if you find anything wrong in my approach.

2016-10-31 16:25:08
O(n^3) works
2016-05-31 19:36:05 vivek singh rana
great problem!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.