Scientists in Antarctica have found a new species! They extracted one sample and took it to the laboratory for testing.

They quickly noticed the species reproduces quite often and that only one parent is required for reproduction. However after the parent reproduces twice, it becomes sterile and cannot reproduce again.

In spite of this, the number of specimens in the laboratory skyrocketed and the need for family trees appeared.

They decided to draw the tree in a simple text editor using the following conventions:

The names of the specimens will be written inside nice boxes using characters -, | and o. The center point of the upper and lower border will be marked by the character +. If the length of the border is even, + will be on the left of the two center points.

o--+--o        o----+----o        o-+--o
|anton|        |anamarija|        |pero|
o--+--o        o----+----o        o-+--o

The boxes will be connected with links. One link connects two or more boxes on their respective + characters, with the parent specimen placed above its children. The boxes and links must not overlap.

+            +                  +
|            |                  |
o        o---o---o        o-----o-----o
|        |       |        |           |
+        +       +        +           +

If the parent has one child, a point to point (leftmost example) link is used. If the parent has two children, a branching link is used, with the older child on the left, and the younger on the right.

Branching links may be expanded in the horizontal direction as long as the number of - characters on both sides stays equal. Links cannot be expanded vertically.

Don't worry, you will not be asked to draw the tree, only determine the number of characters required to draw it. Space characters are not counted, only -, |, +, o and letters in the names.

Input Specification

The first line of input contains one integer ~N~ ~(1 \le N \le 300\,000)~, number of specimens in the laboratory.

The specimens are marked with numbers ~1~ to ~N~ in the order of birth, with the oldest marked ~1~ and youngest marked ~N~.

The next ~N~ lines contain birth notes of all specimens in the order of birth. Each specimen (except the first whose parent is unknown) is described with two pieces of information:

• name - a sequence of at most ~20~ lowercase English alphabet characters
• parent - one integer denoting the parent of this specimen

Output Specification

The first and only line of input should contain the minimal number of characters needed to draw the family tree.

Scoring

Test data worth ~50\%~ of points has ~N < 30~.

Test data worth ~75\%~ of points has ~N < 3\,000~.

Sample Input 1

3
adam
kain 1
abel 1

Sample Output 1

64

Sample Explanation 1

   o-+--o
   |adam|
   o-+--o
     |
  o--o--o
  |     |
o-+--oo-+--o
|kain||abel|
o-+--oo-+--o

Sample Input 2

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

Sample Output 2

371

Sample Explanation 2

                             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