### Problem Statement

"Rack 'em up!" says Jane. She's beaten you at pool again, so you're stuck with the chore of racking the balls for the next game. There are fifteen balls at your disposal, numbered 1 through 15. Those numbered 1 through 7 are called "solids", while 9 through 15 are "stripes". Number 8, the "eight-ball", is neither stripe nor solid.

You are to arrange the balls into five rows such that the first row contains one ball; the second, two balls; and so on. The overall effect is that of an equilateral triangle pointing upward. For the purpose of this problem, we number the positions in the triangle from 0 to 14, starting in the first row and proceeding from left to right, top to bottom. The following piece of ASCII art shows the position numbers.

```
0
1   2
3   4   5
6   7   8   9
10 11  12  13  14
```

In a correct rack, the eight-ball occupies position 4, while positions 10 and 14 may not be occupied by two stripes or two solids. Furthermore, you are at a pool hall whose rules dictate that stripes and solids alternate along the upper left side of the triangle (positions 10, 6, 3, 1, 0); along the fourth row (positions 6, 7, 8, 9); and along the first four positions in the bottom row (positions 10, 11, 12, 13). Finally, positions 5 and 9 must be occupied by two stripes or two solids. In effect, only two patterns of stripes and solids are possible. These patterns are shown below, using X to represent stripes, O for solids, and the numeral 8 for the eight-ball.

```
X                                O
O   O                            X   X
X   8   X                        O   8   O
O   X   O   X                    X   O   X   O
X   O   X   O   O                O   X   O   X   X
```

The balls are, at first, arranged randomly in the triangle. Etiquette demands that you change the configuration only by swapping the positions of two balls at a time. Any two balls, not merely an adjacent pair, may be swapped. Given a int[] describing the initial configuration of the triangle, so that the element at index 0 is the number of the ball at position 0 and so forth, what is the smallest number of swaps required to achieve a correct rack?

### Definition

 Class: Pool Method: rackMoves Parameters: int[] Returns: int Method signature: int rackMoves(int[] triangle) (be sure your method is public)

### Constraints

-triangle contains exactly 15 elements
-each element in triangle is between 1 and 15, inclusive
-triangle contains no duplicates

### Examples

0)

 `{6, 12, 14, 1, 8, 2, 11, 3, 9, 4, 7, 13, 5, 15, 10}`
`Returns: 0`
 This is already a correct rack.
1)

 `{2, 10, 7, 1, 8, 12, 6, 11, 4, 9, 13, 3, 14, 15, 5}`
`Returns: 2`
 The eight-ball is in the right place. We can finish the rack by swapping balls 2 and 10, then 1 and 15.
2)

 `{8, 15, 9, 4, 10, 6, 11, 3, 14, 7, 2, 1, 13, 12, 5}`
`Returns: 3`
 One minimal solution is to swap balls 1 and 13, then 10 and 5, and finally 5 and 8.
3)

 `{15, 5, 8, 13, 2, 14, 10, 3, 4, 6, 7, 9, 1, 12, 11}`
`Returns: 4`
4)

 `{1, 5, 15, 6, 10, 9, 11, 13, 7, 4, 3, 8, 2, 12, 14}`
`Returns: 3`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4620&pm=1809

Eeyore

#### Testers:

lbackstrom , brett1479

Sorting