Chef and Wave
All submissions for this problem are available.
One day Chef's friend gave him a sequence a1,a2,a3,a4.....an. He told Chef to find the length of the longest appearing Even Sequence. An even sequence is a sequence formed with only consecutive even numbers(e.g. 4 8 2 14 is an even sequence but 4 8 5 14 is not). But the twist is that firstly he wants Chef to convert the sequence in a specified form where b1>= b2<=b3 >=b4<=.......... upto n terms and then find the length of the longest appearing Even Sequence.
NOTE: If there are multiple sequence possible, take the one that's lexicographically smallest.
- The first line of input contains one integer N denoting the numbers of Test Cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of element in the Sequence.
- The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the sequence.
output a single line containing the length of the longest appearing Even Sequence.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 105
- 1 ≤ A[i] ≤ 105
2 5 1 2 3 4 5 6 6 7 8 10 12 16
Example case 1:The given sequence can be converted to 2 1 4 3 5, 5 2 3 1 4 etc.. but we'll take the lexicographically smallest one i.e. 2 1 4 3 5.
Now we can see the longest appearing Even Sequence in the new sequence is 1.
Example case 2:Similarly as case 1 the lexicographically smallest sequence is 7 6 10 8 16 12 and the lenght of the longest appearing Even sequence is 5.
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions