Yazoo is a computer game in which you??re given a sequence of integers. A sequence can be broken into one or more subsequences (or subranges) such that the numbers of each subsequence satisfy some arithmetic property. Each subsequence is then given a certain score depending on the property it satisfies and on its length. The properties and their scores are:
A subsequence of length n in which all its numbers are sorted (all non-decreasing or all non-increasing,) is given the score 5 * n.Odd/Even:
A subsequence of length n in which its numbers are all even (or all odd,) is given the score 10 * n.Alternating:
A subsequence of length n in which its numbers alternate between even and odd, is given the score 15 * n.Quads:
A subsequence of length n in which all its numbers are multiple of 4, is given the score 20 * n.
Note the following:
1. A subsequence must be contiguous (similar to substrings of strings). For example, in the sequence [1, 2, 3, 4], [1, 2, 3] is a subsequence whereas [1, 2, 4] isn??t.
2. The minimum length of a subsequence is 3.
3. Any number in the original sequence can be a member of at most one subsequence.
4. It is possible to have some numbers of the original sequence that are not members of any subsequence. In this case, these numbers don??t add anything to the score.
The objective of the game is to break the sequence into subsequences with the maximum total score. For example, the sequence [12, 14, 21, 26, 13, 11, 8] can be broken into the two subsequences [12, 14, 21, 26] (sorted) and [13, 11, 8] (sorted) with a total score of 5 * 4 + 5 * 3 = 35. However, it is better to choose the subsequence [14, 21, 26, 13] (alternating) as its score is 15*4=60. Write a program that determines the maximum total score a sequence can have.Input Format
Your program will be tested on a number of test cases. The first line of the input file contains an integer T representing the number of test cases in the input file. Each test case is described on a single line as a list of integers. The first integer n, is the length of the sequence, and will be followed by n integers, all separated by one or more spaces. A sequence may have up to 1,000 numbers and each number v is in the range -10, 000 < v < +10, 000.Output Format
For each sequence, write on a separate line, the maximum score you can get for that sequence.Sample Input
2 7 12 14 21 26 13 11 8 8 6 5 4 8 12 13 14 15OUTPUT