시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 50.000%

문제

얼마전 남극 연구 탐사진들은 새로운 종을 발견하였다. 연구진은 테스트를 하기 위해 샘플을 하나 추출해 연구실로 보냈다.

이번에 발견된 새로운 종은 짧은 주기를 갖고 번식한다. 번식할 때 부모는 하나만 있으면 된다. 한 부모는 두 번 번식할 수 있으며, 그 이후에는 더 이상 번식할 수 없다.

따라서, 연구실에 있는 표본의 수는 급속도로 늘어났고, 가계도가 필요한 시점이 되었다.

연구진은 간단한 텍스트 에디터를 이용해 가계도를 그리려고 한다. 가계도는 다음과 같은 규칙을 지켜야 한다.

표번의 이름은 '-', '|', 'o'로 이루어진 박스로 둘러쌓여져 있어야 한다. 윗 변과 아랫 변의 중앙에는 '+' 마크가 있어야 한다. 변의 길이가 짝수인 경우에는 두 중앙 중 왼쪽 중앙에 '+'를 표시한다.

박스를 링크를 이용해 연결해야 한다. 한 링크는 두 개 또는 그 이상의 박스를 연결할 수 있으며, '+'와 연결되어 있어야 한다. 부모 박스가 위에, 자식 박스가 아래에 있어야 한다. 박스와 링크는 겹칠 수 없다.

자식의 수가 1개인 경우에는 가장 왼쪽 그림에 나와있는 링크를 사용한다. 둘 이상의 자식을 가지는 경우에는 중간에 갈라진 링크를 사용해야 하며, 왼쪽에는 나이가 많은 자식, 오른쪽에는 적은 자식이 있어야 한다.

링크는 수평방향으로 늘어날 수 있으며, 좌우의 '-'의 개수는 같아야 한다. 링크는 수직방향으로 늘어날 수는 없다.

각 표본의 정보가 주어졌을 때, 가계도를 그리는데 필요한 문자의 개수를 구하는 프로그램을 작성하시오. 단, 공백의 개수는 세지 않으며, '-', '|', '+', 'o', 이름만 센다.

입력

첫째 줄에 실험실에 있는 표본의 수 N (1 ≤ N ≤ 300,000)이 주어진다. 각 표본은 1번부터 N번까지 태어난 순서대로 번호가 매겨져 있다. 즉, 가장 나이가 많은 표본은 1, 어린 표본은 N이다.

다음 N개 줄에는 각 표본의 이름과 부모의 번호가 주어진다. (첫 번째 표본의 부모는 알 수 없다) 이름은 알파벳 소문자로만 이루어진 문자열로 길이는 20을 넘지 않는다.

출력

첫째 줄에 가계도를 그리는데 필요한 글자의 수를 출력한다.

예제 입력

12
anton
ana 1
luka 1
mia 2
tea 3
jakov 3
semiramida 5
dominik 5
anamarija 4
eustahije 4
lovro 2
lovro 11

예제 출력

371

힌트

                             o--+--o 
                             |anton| 
                             o--+--o 
                                | 
                   o------------o------------o 
                   |                         | 
                 o-+-o                     o-+--o 
                 |ana|                     |luka| 
                 o-+-o                     o-+--o 
                   |                         | 
           o-------o-------o              o--o--o 
           |               |              |     | 
         o-+-o          o--+--o         o-+-oo--+--o 
         |mia|          |lovro|         |tea||jakov| 
         o-+-o          o--+--o         o-+-oo--+--o 
           |               |              | 
     o-----o-----o         o        o-----o-----o 
     |           |         |        |           | 
o----+----o o----+----o o--+--oo----+-----o o---+---o 
|anamarija| |eustahije| |lovro||semiramida| |dominik| 
o----+----o o----+----o o--+--oo----+-----o o---+---o