006 - ビルの飾りつけ 3 (Building 3)

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 0 /

TLE
1sec
MLE
256MB
得点
100

問題

　国際情報オリンピックが日本で開かれることとなり，世界の選手達を歓迎するため，空港から宿泊施設までの大通り沿いにある高層ビルを飾りつけることにした．ある著名なデザイナーにデザインを依頼したところ，飾りつけに利用するビルは，空港から宿泊施設に向けて高くなっていく必要があると言った．つまり，飾りつけに利用するビルの高さを空港に近いものから順に h1, h2, h3, ... とおくと，h1 < h2 < h3 < ・・・ となっていなければならない．
　できるだけ飾りつけを華やかにするため，飾りつけに利用するビルの数をできるだけ多くしたい．飾りつけるビルを選ぶ作業を任された JOI 君は，ビルの所有者から「自分の所有するビルは必ず飾りつけに利用してほしい．しかも，ビルが目立つように，飾りつけに利用されるビルの中でそのビルが最も宿泊施設に近くなるようにしてほしい．」という無茶な要求をされる可能性に思い当たった．
　空港から宿泊施設までの大通り沿いには N 個のビルがあり，空港から i 番目 (1 ≤ i ≤ N) に近いビルをビル i と呼ぶことにする．N 個のビルの高さは全て異なる．JOI 君はどのような要求がきても大丈夫なように「ビル i を飾りつけに利用し，しかも飾りつけに利用されるビルの中でビル i が最も宿泊施設に近くなるようにビルを選ぶとき，選べるビルの個数は最大で Ai 個である」ということをあらかじめ計算しておいた．JOI 君はそのようにして計算した整数列 A1, A2, ..., AN をメモして，情報オリンピック日本委員会の K 理事長に提出した．
　しかし，K 理事長が受け取ったメモには，実際には，長さ N - 1 の整数列 B1, B2, ..., BN-1 しか書かれていなかった．K 理事長はビルの高さの情報を知らないので，Ai の値を計算することはできない．
　K 理事長は，JOI 君が数を 1 個書き忘れたに違いないと考えた．整数列 A1, A2, ..., AN としてはビルの高さによって様々なものが考えられる．これらのうち，整数列から 1 箇所の値を取り除いたものが整数列 B1, B2, ..., BN-1 になるものは何通りあるだろうか．
　ただし，実際には，JOI 君は他にも書き損じをしているかもしれない．B1, B2, ..., BN-1 の値によっては，そのようなものが 1 個もないこともあるかもしれない．

課題

　長さ N - 1 の整数列 B1, B2, ..., BN-1 が与えられる．整数列 A1, A2, ..., AN として考えられるもののうち，1 箇所の値を取り除いたものが整数列 B1, B2, ..., BN-1 になるものが何通りあるかを求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

  • 1 行目には整数 N が書かれている．これは空港から宿泊施設までの大通り沿いにビルが N 個あることを表す．
  • 続く N - 1 行のうちの j 行目 (1 ≤ j ≤ N - 1) には，整数 Bj が書かれている．これは K 理事長が受け取ったメモに書かれた整数列の j 番目の値である．

出力

　標準出力に，整数列 A1, A2, ..., AN として考えられるもののうち，1 箇所の値を取り除いたものが整数列 B1, B2, ..., BN-1 になるものの個数を表す整数を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす．

  • 2 ≤ N ≤ 1 000 000．
  • 1 ≤ Bj ≤ N (1 ≤ j ≤ N - 1)．

小課題

小課題 1 [10 点]

  • N ≤ 8 を満たす．

小課題 2 [30 点]

  • N ≤ 300 を満たす．

小課題 3 [60 点]

　追加の制約はない．

入出力例

入力例 1

4
1
1
2

出力例 1

5

　空港から宿泊施設までの大通り沿いには 4 個のビルがある．ビル i の高さを Hi とする．
　整数列 A1, A2, A3, A4 としてはビルの高さによって様々なものが考えられる．これらのうち，整数列から1 箇所の値を取り除いたものが整数列 1, 1, 2 になるものは次の 5 通りである．

  • 整数列 1, 2, 1, 2．例えば H2 > H4 > H1 > H3 のとき，A1 = 1, A2 = 2, A3 = 1, A4 = 2 となる．また，H2 > H1 > H4 > H3 のときも，A1 = 1, A2 = 2, A3 = 1, A4 = 2 となる．
  • 整数列 1, 1, 2, 3．例えば H4 > H3 > H1 > H2 のとき，A1 = 1, A2 = 1, A3 = 2, A4 = 3 となる．
  • 整数列 1, 1, 2, 1．例えば H3 > H1 > H2 > H4 のとき，A1 = 1, A2 = 1, A3 = 2, A4 = 1 となる．
  • 整数列 1, 1, 2, 2．例えば H3 > H4 > H1 > H2 のとき，A1 = 1, A2 = 1, A3 = 2, A4 = 2 となる．
  • 整数列 1, 1, 1, 2．例えば H4 > H1 > H2 > H3 のとき，A1 = 1, A2 = 1, A3 = 1, A4 = 2 となる．

入力例 2

8
1
1
2
1
2
3
1

出力例 2

15