BORW  Black or White
“It’s Black, It’s White, It’s Tough For You To Get By”
Michael Jackson (19582009)
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 ≤ 10^{6} 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
hide comments
dhairya_2000:
20191210 17:50:15
AC in 1 go !! 

kd2636:
20190928 12:47:08
I need more help on this. I constructed a backtracking solution but it's getting tle. Any hint how shuld I optimize it. My recursive function does not return therefore I am not able to do any memorization. 

amannegi227:
20190711 13:56:29
what about Palindromic Pattern ? 

akibk001:
20190417 11:12:35
weak test cases


ab_biswas09:
20190317 19:14:07
AC in one Go => 1.91 s 

f00zz:
20190316 22:33:03
Forget about trying to solve it in Python... 

eagleshadow:
20190228 20:08:10
Very nice problem 

sherlock11:
20180531 16:14:22
i think problem with LIS/LDS is that an array may have more than one LIS/LDS hence simply finding LIS and LDS will result in WA...instead think that each element can be included either in increasing sequence or decreasing sequence or not include it at all.............by the way i have special place for MJ in my heart.. we both share same birthday......."RIP MJ" 

learnerinblack:
20180530 12:57:57
What's problem with LIS/LDS? 

amulyagaur:
20171211 11:21:28
“It’s Black, It’s White, It’s Tough For You To Get By”....... indeed it was.....a silly mistake wasted many hours :/ 
Added by:  Pablo Ariel Heiber 
Date:  20100822 
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 