AtCoder Beginner Contest 026

C - 高橋君の給料


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君は、社員が N 人いる会社の社長です。高橋君の会社では、以下のように給料が決まっています。

  • 高橋君を含む社員の全員が、 1 から N までの社員番号を持っている。高橋君の社員番号はもちろん 1 である。
  • 高橋君以外の社員には、必ず自分より社員番号が小さい上司がただ一人存在する。自分が上司になっている社員のことを、直属の部下と呼ぶ。
  • 直属の部下がいない社員の給料は 1 であり、直属の部下がいる社員の給料は 、{\rm max}(その社員の直属の部下の給料) + {\rm min}(その社員の直属の部下の給料) + 1 である。直属の部下が一人しかいない場合は、その部下の給料の 2 倍 + 1 が、その社員の給料となる。

この時、高橋君の給料を求めなさい。


入力

入力は以下の形式で標準入力から与えられる。

N
B_2
B_3
:
B_N
  • 1 行目には、社員の数を表す整数 N (1≦N≦20) が与えられる。
  • 2 行目からの N-1 行には、各社員の上司の情報が与えられる。このうち i 行目には、 社員番号 i + 1 番の社員の上司の社員番号を表す整数 B_i(1≦B_i≦i) が、 1 行で与えられる。

出力

高橋君の給料を 1 行で出力しなさい。 出力の末尾には改行を入れること。


入力例1

5
1
1
1
1

出力例1

3

高橋君は、直属の部下が 4 人いますが、その全ての部下の給料が 1 です。よって、高橋君の給料は、1 + 1 + 1 = 3となります。


入力例2

7
1
1
2
2
3
3

出力例2

7

社員番号 2, 3 の二人の社員が二人部下を持ち、その二人の上司が高橋君、という構成です。 ほかの社員の給料は 1 なので、社員番号 2, 3 の二人の社員の給料は 1 + 1 + 1 = 3 となります。 よって、高橋君の給料は、 3 + 3 + 1 = 7 となります。


入力例3

6
1
2
3
3
2

出力例3

11

高橋君の直属の部下は、社員番号 2 の社員一人だけです。 この社員の直属の部下は、社員番号 3, 6 の二人の社員です。 この二人の給料はそれぞれ 3, 1 なので、社員番号 2 の社員の給料は 5 です。 よって、高橋君の給料は、 5+5+1 = 11 となります。


入力例4

10
1
2
3
4
5
6
7
8
9

出力例4

1023

高橋君の給料は非常に多くなることがあります。


Submit提出する