시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 5 5 5 100.000%

문제

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

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