Sorting is done by moving one card at a time from its current position to a new position in the hand, at the start, end, or in between two adjacent cards. What is the smallest number of moves required to sort a given hand of cards?
The first line of input contains an integer $n$ ($1 \le n \le 52$), the number of cards in the hand. The second line contains $n$ pairwise distinct space-separated cards, each represented by two characters. The first character of a card represents the rank and is either a digit from 2 to 9 or one of the letters T, J, Q, K, and A representing Ten, Jack, Queen, King and Ace, respectively, given here in increasing order. The second character of a card is from the set {s, h, d, c} representing the suits spades $\spadesuit $, hearts $\heartsuit $, diamonds $\diamondsuit $, and clubs $\clubsuit $.
Output the minimum number of card moves required to sort the hand as described above.
Sample Input 1 | Sample Output 1 |
---|---|
4 2h Th 8c Qh |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
7 9d As 2s Qd 2c Jd 8h |
2 |
Sample Input 3 | Sample Output 3 |
---|---|
4 2h 3h 9c 8c |
0 |