Ernest Vincent Wright was an American author, known for writing a novel (Gadsby) without using
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
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:
xdeletes 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.
hmoves the cursor one step backward (to the left). Nothing happens if the cursor is at the beginning of the document.
fwaits for the user to input another character , and then moves the cursor forward to the next occurrence of (even if the character at the cursor happens to be ). Nothing happens if does not occur anywhere to the right of the cursor position.
For example, if the current text is
where the cursor is denoted by a frame , then
xwould give jeffehadabigidea
hwould give jeffehadabigidea
fiwould give jeffehadabigidea
Write a program that calculates the least number of key presses that Victor needs to use to delete
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.
The first line contains the integer , the length of the document. The next line contains characters,
each one of the ten lowercase letters from
j. The first and the last letter of the input are both
The only line of output should contain exactly one integer: the least number of key presses Victor
needs to delete all the
In test cases worth points:
In test cases worth additional points:
Explanation for Sample Output
An optimal solution for the example test case is: