Olimpiade Informatika Internasional akan diselenggarakan di Jepang. Untuk menyambut para peserta dari seluruh dunia, diputuskan untuk menghias gedung-gedung tinggi di sepanjang jalan utama dari bandara menuju tempat penginapan. Ketika seorang perancang terkenal diminta membuat rancangan, ia mengatakan bahwa gedung-gedung yang digunakan untuk hiasan harus semakin tinggi dari arah bandara menuju penginapan. Dengan kata lain, jika tinggi gedung-gedung yang digunakan untuk hiasan, dalam urutan dari yang terdekat dengan bandara, adalah $h_1, h_2, h_3, \ldots$, harus berlaku $h_1 < h_2 < h_3 < \cdots$.

Agar hiasannya semeriah mungkin, jumlah gedung yang digunakan ingin dibuat sebanyak mungkin. JOI-kun, yang ditugaskan memilih gedung untuk dihias, menyadari bahwa seorang pemilik gedung mungkin memberikan permintaan yang tidak masuk akal: “Gedung milik saya harus digunakan untuk hiasan. Selain itu, agar gedung itu menonjol, saya ingin gedung saya menjadi yang paling dekat dengan penginapan di antara gedung-gedung yang digunakan untuk hiasan.”

Ada $N$ gedung di sepanjang jalan utama dari bandara ke penginapan. Gedung ke-$i$ ($1 \le i \le N$) terdekat dari bandara disebut gedung $i$. Tinggi semua $N$ gedung berbeda. Untuk bersiap menghadapi permintaan apa pun, JOI-kun telah menghitung sebelumnya bahwa “jika gedung $i$ harus digunakan untuk hiasan dan menjadi gedung terdekat dengan penginapan di antara gedung yang digunakan, jumlah maksimum gedung yang dapat dipilih adalah $A_i$.” JOI-kun mencatat barisan bilangan bulat $A_1, A_2, \ldots, A_N$ yang dihitungnya dan menyerahkannya kepada ketua K dari Komite Olimpiade Informatika Jepang.

Namun, catatan yang diterima ketua K ternyata hanya memuat barisan bilangan bulat $B_1, B_2, \ldots, B_{N-1}$ sepanjang $N - 1$. Karena ketua K tidak mengetahui tinggi gedung-gedung tersebut, ia tidak dapat menghitung nilai $A_i$.

Ketua K menduga bahwa JOI-kun pasti lupa menulis satu bilangan. Ada berbagai kemungkinan barisan $A_1, A_2, \ldots, A_N$, bergantung pada tinggi gedung-gedungnya. Di antara kemungkinan tersebut, berapa banyak barisan yang menjadi $B_1, B_2, \ldots, B_{N-1}$ setelah satu nilai pada suatu posisi dihapus?

Namun, JOI-kun mungkin juga melakukan kesalahan penulisan lainnya. Bergantung pada nilai $B_1, B_2, \ldots, B_{N-1}$, mungkin tidak ada satu pun barisan seperti itu.

Tugas

Diberikan barisan bilangan bulat $B_1, B_2, \ldots, B_{N-1}$ sepanjang $N - 1$. Tulislah program untuk menghitung banyaknya kemungkinan barisan $A_1, A_2, \ldots, A_N$ yang menjadi $B_1, B_2, \ldots, B_{N-1}$ setelah satu nilai pada suatu posisi dihapus.

Masukan

Bacalah masukan berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N$. Ini menyatakan bahwa ada $N$ gedung di sepanjang jalan utama dari bandara ke penginapan.
• Baris ke-$j$ ($1 \le j \le N - 1$) dari $N - 1$ baris berikutnya berisi bilangan bulat $B_j$. Ini adalah nilai ke-$j$ dalam barisan bilangan bulat yang tertulis pada catatan yang diterima ketua K.

Keluaran

Tuliskan satu baris ke keluaran standar yang berisi sebuah bilangan bulat, yaitu banyaknya kemungkinan barisan $A_1, A_2, \ldots, A_N$ yang menjadi $B_1, B_2, \ldots, B_{N-1}$ setelah satu nilai pada suatu posisi dihapus.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $2 \le N \le 1\,000\,000$.
• $1 \le B_j \le N$ ($1 \le j \le N - 1$).

Subsoal

Subsoal 1 [10 poin]

• Memenuhi $N \le 8$.

Subsoal 2 [30 poin]

• Memenuhi $N \le 300$.

Subsoal 3 [60 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

4
1
1
2

Keluaran 1

5

Penjelasan

Ada 4 gedung di sepanjang jalan utama dari bandara ke penginapan. Misalkan tinggi gedung $i$ adalah $H_i$.

Ada berbagai kemungkinan barisan $A_1, A_2, A_3, A_4$, bergantung pada tinggi gedung-gedungnya. Di antara kemungkinan tersebut, ada lima barisan berikut yang menjadi barisan $1, 1, 2$ setelah satu nilai pada suatu posisi dihapus.

• Barisan $1, 2, 1, 2$. Misalnya, jika $H_2 > H_4 > H_1 > H_3$, maka $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Jika $H_2 > H_1 > H_4 > H_3$, hasilnya juga $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Barisan $1, 1, 2, 3$. Misalnya, jika $H_4 > H_3 > H_1 > H_2$, maka $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Barisan $1, 1, 2, 1$. Misalnya, jika $H_3 > H_1 > H_2 > H_4$, maka $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Barisan $1, 1, 2, 2$. Misalnya, jika $H_3 > H_4 > H_1 > H_2$, maka $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Barisan $1, 1, 1, 2$. Misalnya, jika $H_4 > H_1 > H_2 > H_3$, maka $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Masukan 2

8
1
1
2
1
2
3
1

Keluaran 2

15