問題文

AtCoder 社のオフィスは N 個の部屋を N - 1 本の廊下で結んだ木構造をしています。 廊下 i は部屋 V_i と部屋 i + 1 を双方向に結んでいます。

あなたはオフィスの N 個の部屋から異なる 3 個の部屋を選び金庫を設置しました。 さらに、各部屋 v に対して、部屋 v とそれぞれの金庫が設置された部屋の距離を計算し、その中央値 M_v を記録しました。 しかし、その後、どの部屋に金庫を設置したか忘れてしまいました。

オフィスの構造および各部屋 v に対する値 M_v が与えられます。 金庫の設置場所として考えられるような異なる 3 個の部屋の組の個数を求めてください。

なお、部屋 x と部屋 y の距離とは、部屋 x から部屋 y へ廊下を通って移動する際に通る廊下の本数の最小値のことです。

制約

• 3 \leq N \leq 100,000
• 1 \leq V_i \leq i (1 \leq i \leq N - 1)
• 1 \leq M_v \leq N - 1 (1 \leq v \leq N)
• 入力値はすべて整数である。

入力例 1

8
1
2
1
4
1
6
4
2
1
2
1
2
3
4
2

出力例 1

2

条件を満たす部屋の組は (部屋 1, 部屋 3, 部屋 5) と (部屋 1, 部屋 3, 部屋 8) の 2 個あります。

入力例 2

5
1
2
3
4
1
1
1
1
1

出力例 2

0