Stacking Pancakes

Time limit2sMemory limit256 MB

Summary

Given a stack of up to 6 pancakes with distinct sizes and sides, find the minimum number of prefix flips to sort sizes descending and turn all fronts up.

Level: Medium6 of 10
Topics: BFS, Brute force, Simulation
Solved: No attempts yet

Problem

Jiyong is a baker who is good at making pancakes. One day he baked $N$ pancakes, all of different sizes, each with a front side and a back side you can tell apart. Listed from smallest to largest, their sizes are $1, 2, \dots, N$ . Jiyong stacked them in the reverse of the order he baked them without thinking about it, so the stack may not be sorted by size. He wants to use the smallest number of flips to reach a stack whose sizes decrease toward the top and whose pancakes all have the front side up.

A flip works like this. Pick an $i$ with $1 \le i \le N$ , lift the top $i$ pancakes together, and turn them over. The order of those $i$ pancakes reverses and each of them changes the side that faces up. For example, if the stack from the top is 1(+) 2(+) 3(+) 4(+) 5(+) and you pick $i = 3$ , it becomes 3(-) 2(-) 1(-) 4(+) 5(+). Here + means the front side faces up and - means the back side faces up.

Help Jiyong and find the minimum number of flips he needs.

Input

The first line contains the number of pancakes $N$ . ( $1 \le N \le 6$ )

Each of the next $N$ lines describes one pancake of the stack, from the top down, giving its size and its current facing separated by a space. The facing is + if the front side faces up and - if the back side faces up. Each of the sizes $1$ through $N$ appears exactly once.

Output

Print the minimum number of flips that reaches the required stack, on one line.

Examples2

Example 1
Input
```
5
1 +
2 +
3 +
4 +
5 +
```
Expected output
```
0
```
Example 2
Input
```
5
1 +
2 -
3 +
4 +
5 +
```
Expected output
```
3
```