Baltic Olympiad in Informatics: 2013 Day 2, Problem 3

Ernest Vincent Wright was an American author, known for writing a novel (Gadsby) without using the letter e. Victor is a big fan of Ernest and tries to imitate him in writing a novel, but is looking for a real challenge. He uses only the first ten characters of the alphabet (namely abcdefghij). Ironically, the e key on his computer breaks halfway through the novel, and for consistency, he decides to delete all the es he has already written. His friend, a programmer, recommended him to use the text editor Vim to perform this task. Unfortunately, Victor is not very familiar with Vim, and knows only three different commands: x, h and f.

• x deletes the character at the cursor. The cursor position (counted from the left) does not change. Victor shall not use this command if the cursor is at the last character of the document.
• h moves the cursor one step backward (to the left). Nothing happens if the cursor is at the beginning of the document.
• f waits for the user to input another character ~C~, and then moves the cursor forward to the next occurrence of ~C~ (even if the character at the cursor happens to be ~C~). Nothing happens if ~C~ does not occur anywhere to the right of the cursor position.

For example, if the current text is

jeff~[~i~]~ehadabigidea

where the cursor is denoted by a frame ~[]~, then

• x would give jeff~[~e~]~hadabigidea
• h would give jef~[~f~]~ehadabigidea
• fi would give jeffehadab~[~i~]~gidea

Write a program that calculates the least number of key presses that Victor needs to use to delete all the es in the document, but no other letters. Initially, the cursor is at the first character of the document. Note that the e key is broken, so the command fe cannot be used.

Input

The first line contains the integer ~N~, the length of the document. The next line contains ~N~ characters, each one of the ten lowercase letters from a to j. The first and the last letter of the input are both different from e.

Output

The only line of output should contain exactly one integer: the least number of key presses Victor needs to delete all the es.

Constraints

~N \le 70\,000~

In test cases worth ~50~ points: ~N \le 500~

In test cases worth additional ~10~ points: ~N \le 5\,000~

Sample Input

35
chefeddiefedjeffeachbigagedegghehad

Sample Output

36

Explanation for Sample Output

An optimal solution for the example test case is: fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx