Snowmen#1872
Winter, 2012. Amidst news about the approaching apocalypse and the end of the world, a breakthrough in snowman cloning technology went largely unnoticed. As you may know, a snowman consists of zero or more balls stacked vertically on top of each other, and cloning refers to the process of creating an identical copy (clone).
In the town of Mestyachkovo, the teacher Andrey Sergeevich purchased a snowman cloning device from the online store "Internet Shop of Cloning Devices." Now, children are able to play the following game in the yard. From time to time, one of them selects a snowman they like, clones it, and then:
either adds a new ball on top;
or removes the top ball (if the snowman is not empty).
The teacher Andrey Sergeevich has recorded the entire sequence of actions and now wants to know the total mass of all the built snowmen.
The first line contains the number of actions (1 \leq n \leq 200\,000). Each of the following lines describes an action:
— clone snowman number (0 \leq t < i) and add a ball of mass (0 < m \leq 1000) on top;
— clone snowman number (0 \leq t < i) and remove the top ball. It is guaranteed that the snowman is not empty.
Action number (described in line i+1) results in the creation of snowman number . Initially, there is an empty snowman numbered zero.
All input numbers are integers.
Print the total mass of all built snowmen.
Example 1