Vim

미국의 소설가 어니스트 빈센트 라이트는 알파벳 e를 한 번도 쓰지 않고 소설 《개즈비》를 완성했다.

상근이가 가장 좋아하는 소설가도 어니스트다. 요즘 상근이는 알파벳의 처음 10글자(a부터 j까지)만 사용해 소설을 쓰고 있다.

그런데 어느 날 상근이의 키보드에서 e키가 망가졌다. 새 키보드를 살 돈이 없는 상근이는, 지금까지 쓴 원고에 들어 있는 e를 모두 지우기로 했다. 친구 선영이는 Vim을 쓰면 쉽게 지울 수 있다고 알려 주었다.

상근이가 아는 Vim 명령어는 x, h, f 세 가지뿐이다.

• x : 커서가 가리키는 글자를 삭제한다. 삭제한 뒤에도 커서의 위치(인덱스)는 그대로여서, 삭제된 글자 바로 다음에 있던 글자를 가리키게 된다. 그래서 커서가 문서의 마지막 글자를 가리키고 있을 때는 이 명령을 쓸 수 없다.
• h : 커서를 왼쪽으로 한 칸 옮긴다. 이미 첫 글자를 가리키고 있으면 커서는 움직이지 않는다.
• f : 이 키를 누른 뒤에는 글자 C를 이어서 입력해야 한다. 커서보다 뒤에 있으면서 가장 가까운 C로 커서를 옮긴다. 커서 뒤에 C가 없으면 커서는 제자리에 머문다.

누른 키의 횟수는 x와 h가 각각 1번, f는 뒤따르는 글자까지 합쳐 2번으로 센다.

예를 들어 아래와 같이 텍스트와 커서 위치가 주어졌다고 하자. 커서가 가리키는 글자는 대괄호 [ ]로 표시한다.

jeff[i]ehadabigidea

• x를 누르면 jeff[e]hadabigidea가 된다.
• h를 누르면 jef[f]iehadabigidea가 된다.
• fi를 누르면 jeffiehadab[i]gidea가 된다.

문서가 주어졌을 때, 문서에 있는 모든 e를 지우기 위해 키를 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하라. e가 아닌 글자는 지우면 안 된다. 처음에 커서는 문서의 첫 글자를 가리킨다. e키가 망가졌으므로 fe 명령은 사용할 수 없다.

첫째 줄에 문서의 길이 N이 주어진다. 둘째 줄에는 문서의 내용이 주어진다. 문서는 a부터 j까지의 알파벳 소문자로만 이루어지며, 첫 글자와 마지막 글자는 e가 아니다. ($N \le 70000$)

문서에 있는 모든 e를 지우기 위해 눌러야 하는 키의 최소 횟수를 첫째 줄에 출력한다.

첫 번째 예제 문서에서는 fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx(키 36번)를 눌러 모든 e를 지울 수 있다.

이 문제에서 설명한 명령들은 모두 실제 Vim 명령이다.