問題文

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

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

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

入力例1Copy

5
1
1
1
1

出力例1Copy

3

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

入力例2Copy

7
1
1
2
2
3
3

出力例2Copy

7

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

入力例3Copy

6
1
2
3
3
2

出力例3Copy

11

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

入力例4Copy

10
1
2
3
4
5
6
7
8
9

出力例4Copy

1023

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