#857 Vassals

Statement

Statement language

The lord also ought to act toward his faithful vassal reciprocally in all these things.

Fulbert of Chartres, letter to William, Duke of Aquitaine (1020)

You are an official responsible for the roads in a kingdom, and the highwaymen who have recently begun to infest them are giving you a headache. To address this situation, the king intends to order the lords under his command to provide knights and form guard units to maintain order and safety on the roads. However, the number of knights each lord can provide varies, so it may not be possible to assign knights to every road.

There are $N$ lords, including the king, numbered from $1$ to $N$ . Lord $1$ is the king. Each lord other than the king serves exactly one liege and is that liege's vassal. Starting from any lord and repeatedly following their liege always leads to the king.

Each lord governs a piece of land called an estate. The liege of lord $i$ is lord $P_i$ , and each lord other than the king has their estate connected to their liege's estate by one road.

The kingdom may also have roads connecting the estates of lords who are not each other's liege and vassal. However, the king wishes to prioritize protecting travel between lieges and vassals. Therefore, guard units may be assigned only to the roads connecting a lord's estate to their liege's estate. All other roads are ignored in this problem.

A guard unit assigned to a road consists of two knights, one provided by each lord at its endpoints. Lord $i$ can provide $B_i$ knights to help maintain order. Each knight may join at most one guard unit, and at most one guard unit may be assigned to each road. Not every knight needs to be assigned.

A road with a guard unit assigned to it is safe. Find the maximum possible number of safe roads among the eligible roads.

Input

The first line contains the number of lords $N$ .

The second line contains $P_2,P_3,\ldots,P_N$ , separated by spaces.

Output

Print the maximum possible number of safe roads.

Constraints

$2\le N\le200\,000$
$1\le P_i\le N$

Samples

Sample 1

Input

6
1 1 2 2 3
1 2 1 1 1 1

Output

In the first example, guard units can be assigned to the roads between estates $2$ and $4$ , between estates $2$ and $5$ , and between estates $3$ and $6$ . Every eligible road is incident to estate or , and these two lords can provide a total of only knights. Therefore, guard units cannot be assigned to or more roads.