Building 3

国際情報オリンピックが日本で開かれることとなり，世界の選手達を歓迎するため，空港から宿泊施設 までの大通り沿いにある高層ビルを飾りつけることにした．ある著名なデザイナーにデザインを依頼した ところ，飾りつけに利用するビルは，空港から宿泊施設に向けて高くなっていく必要があると言った．つ まり，飾りつけに利用するビルの高さを空港に近いものから順に 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)．