Card game

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fewest single-card moves to group the hand by suit with each suit sorted by number, and put the cyan cards last in increasing order.

Level: Medium5 of 10
Topics: Dynamic programming, Binary search, Array
Solved: No attempts yet

Statement

The Olympic Games in Paris are almost here, and you are thrilled! You and four of your friends managed to get five of the rare tickets for sports climbing, even though all tickets sold out in less than two hours. While you wait for the games to start, you decide to play your favourite card game.

The card deck has four standard suits in different colours: silver (S), white (W), emerald (E), and red (R). It also has one trump suit, cyan (C). Cyan cards outrank all other cards. Each suit has $N$ cards numbered from $1$ to $N$ , so the deck has $5N$ cards in total. At the start of the game, the deck is dealt randomly among five players, with $N$ cards each.

Before you play, you want to organise your hand. Cards of the same suit must be next to each other in increasing order, and the trump cards must come last, also in increasing order. The cards arrive as a sequence. In one action, you take one card out of your hand and put it back at another position: between two cards, before the first card, or after the last card.

Find the minimum number of actions needed to organise your hand.

Input

The input has two lines. The first line contains $N$ . The second line contains $N$ space-separated values. Each value is one letter from {S, W, E, R, C} for the suit, followed by an integer $V$ with $1 \le V \le N$ for the card number.

Output

Print a single line with the minimum number of actions.

Constraints

$1 \le N \le 100\,000$

Examples2

Example 1
Input
```
4
C1 R2 E4 R1
```
Expected output
```
2
```
Example 2
Input
```
5
S2 W4 E1 R5 C1
```
Expected output
```
0
```