### Problem Statement

A numerical sequence is called a palindrome if the reverse of the sequence is the same as the original. For example sequences {1, 2, 1}, {15, 78, 78, 15} and {112} are palindromes, but {1, 2, 2}, {15, 78, 87, 51} and {112, 2, 11} are not.

You will be given a int[] sequence. You can replace any two adjacent numbers with their sum. Your method should return a minimal number of such operations required to make the given sequence a palindrome.

### Definition

 Class: NumericalSequence Method: makePalindrome Parameters: int[] Returns: int Method signature: int makePalindrome(int[] sequence) (be sure your method is public)

### Constraints

-sequence will contain between 1 and 50 elements, inclusive.
-Each element of sequence will be between 1 and 10000, inclusive.

### Examples

0)

 `{15,78,78,15}`
`Returns: 0`
 The sequence is a palindrome already.
1)

 `{1,1,1,3}`
`Returns: 2`
 We should replace two ones with 2 and afterwards replace 2 and 1 with 3.
2)

 `{15,78,87,51}`
`Returns: 3`
3)

 `{3,23,21,23,42,39,63,76,13,13,13,32,12,42,26}`
`Returns: 8`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4619

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8012&pm=4619

Andrew_Lazarev

#### Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Greedy