Under construction

Still being built. Things may change

Digital TV

Time limit1sMemory limit128 MB

Summary
Compute the minimum button presses to move KBS1 to position 1 and KBS2 to position 2 in a channel list using arrow move and swap operations.
Level

Medium5 of 10

Topics
Greedy, Simulation, Array
Solved
No attempts yet

Problem

Sang-geun just bought a new digital receiver and wants to make KBS1 the first channel and KBS2 the second channel in his list of available channels. Every channel has a distinct name, and the list always contains both KBS1 and KBS2.

To the left of the list there is an arrow that points at the currently selected channel. Initially the arrow points at the topmost channel. The following four buttons rearrange the list.

  1. Move the arrow down by one (from channel ii to i+1i+1).
  2. Move the arrow up by one (from channel ii to i−1i-1).
  3. Move the currently selected channel down by one (swap channels ii and i+1i+1; the arrow then points at i+1i+1).
  4. Move the currently selected channel up by one (swap channels ii and i−1i-1; the arrow then points at i−1i-1).

A button that would move the arrow outside the list is ignored.

You only need to make KBS1 the first channel and KBS2 the second channel; the order of the remaining channels does not matter. Write a program that finds the minimum number of button presses required to achieve this.

Input

The first line contains the number of channels NN (2≤N≤1002 \le N \le 100). Each of the next NN lines contains one channel name, given in the current list order. Each channel name is at most 1010 characters long and consists only of uppercase letters and digits. The input never has KBS1 already in the first position and KBS2 already in the second position at the same time.

Output

Print, on a single line, the minimum number of button presses needed to make KBS1 the first channel and KBS2 the second channel.

Examples5

  1. Example 1

    Input
    3
    MBC
    KBS1
    KBS2
    
    Expected output
    2
    
  2. Example 2

    Input
    4
    ABC1
    ABC02
    KBS2
    KBS1
    
    Expected output
    8
    
  3. Example 3

    Input
    2
    KBS2
    KBS1
    
    Expected output
    1
    
  4. Example 4

    Input
    5
    KBS1
    AAA
    BBB
    CCC
    KBS2
    
    Expected output
    7
    
  5. Example 5

    Input
    6
    AA
    BB
    KBS1
    KBS2
    CC
    DD
    
    Expected output
    8