Olympic Tin học Quốc tế sẽ được tổ chức tại Nhật Bản. Để chào đón các thí sinh từ khắp thế giới, ban tổ chức quyết định trang trí các tòa nhà cao tầng dọc theo đại lộ từ sân bay đến nơi lưu trú. Khi được nhờ thiết kế, một nhà thiết kế nổi tiếng cho biết các tòa nhà được chọn để trang trí phải cao dần theo hướng từ sân bay đến nơi lưu trú. Nói cách khác, nếu chiều cao của các tòa nhà được trang trí, theo thứ tự từ gần sân bay nhất, là $h_1,h_2,h_3,\ldots$, thì phải có $h_1<h_2<h_3<\cdots$.
Để việc trang trí lộng lẫy nhất có thể, ban tổ chức muốn số tòa nhà được trang trí càng nhiều càng tốt. JOI, người được giao chọn các tòa nhà, nhận ra rằng chủ một tòa nhà có thể đưa ra yêu cầu vô lý như sau: “Nhất định phải dùng tòa nhà của tôi để trang trí. Hơn nữa, để tòa nhà nổi bật, tôi muốn nó là tòa nhà gần nơi lưu trú nhất trong số các tòa nhà được trang trí.”
Có $N$ tòa nhà dọc theo đại lộ từ sân bay đến nơi lưu trú. Gọi tòa nhà gần sân bay thứ $i$ ($1\le i\le N$) là tòa nhà $i$. Chiều cao của cả $N$ tòa nhà đều khác nhau. Để có thể đáp ứng bất kỳ yêu cầu nào, JOI đã tính trước rằng: “Nếu chọn các tòa nhà sao cho tòa nhà $i$ được trang trí và là tòa nhà gần nơi lưu trú nhất trong số các tòa nhà được trang trí, thì số tòa nhà tối đa có thể chọn là $A_i$.” JOI ghi dãy số nguyên $A_1,A_2,\ldots,A_N$ tính được vào một tờ ghi chú và nộp cho chủ tịch K của Ủy ban Olympic Tin học Nhật Bản.
Tuy nhiên, tờ ghi chú mà chủ tịch K nhận được thực ra chỉ có dãy số nguyên $B_1,B_2,\ldots,B_{N-1}$ dài $N-1$. Vì không biết chiều cao của các tòa nhà, chủ tịch K không thể tính các giá trị $A_i$.
Chủ tịch K cho rằng JOI chắc chắn đã quên viết một số. Tùy theo chiều cao các tòa nhà, có nhiều dãy $A_1,A_2,\ldots,A_N$ có thể có. Trong số đó, có bao nhiêu dãy mà khi xóa giá trị tại một vị trí sẽ thu được dãy $B_1,B_2,\ldots,B_{N-1}$?
Tuy nhiên, JOI cũng có thể đã mắc lỗi ghi chép khác. Tùy theo các giá trị $B_1,B_2,\ldots,B_{N-1}$, có thể không có dãy nào như vậy.
Nhiệm vụ
Cho dãy số nguyên $B_1,B_2,\ldots,B_{N-1}$ dài $N-1$. Hãy viết chương trình tính số dãy có thể có $A_1,A_2,\ldots,A_N$ mà khi xóa giá trị tại một vị trí sẽ thu được dãy $B_1,B_2,\ldots,B_{N-1}$.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
- Dòng đầu tiên chứa số nguyên $N$, cho biết có $N$ tòa nhà dọc theo đại lộ từ sân bay đến nơi lưu trú.
- Dòng thứ $j$ ($1\le j\le N-1$) trong $N-1$ dòng tiếp theo chứa số nguyên $B_j$. Đây là giá trị thứ $j$ của dãy số nguyên được ghi trên tờ ghi chú mà chủ tịch K nhận được.
Dữ liệu ra
In ra đầu ra chuẩn một dòng chứa số nguyên là số dãy có thể có $A_1,A_2,\ldots,A_N$ mà khi xóa giá trị tại một vị trí sẽ thu được dãy $B_1,B_2,\ldots,B_{N-1}$.
Giới hạn
Tất cả dữ liệu vào thỏa mãn các điều kiện sau.
- $2\le N\le 1\,000\,000$.
- $1\le B_j\le N$ ($1\le j\le N-1$).
Nhiệm vụ con
Nhiệm vụ con 1 [10 điểm]
- Thỏa mãn $N\le8$.
Nhiệm vụ con 2 [30 điểm]
- Thỏa mãn $N\le300$.
Nhiệm vụ con 3 [60 điểm]
Không có giới hạn bổ sung.
Ví dụ
Dữ liệu vào 1
4 1 1 2
Dữ liệu ra 1
5
Ghi chú
Có 4 tòa nhà dọc theo đại lộ từ sân bay đến nơi lưu trú. Gọi chiều cao của tòa nhà $i$ là $H_i$.
Tùy theo chiều cao các tòa nhà, có nhiều dãy $A_1,A_2,A_3,A_4$ có thể có. Trong số đó, có 5 dãy sau mà khi xóa giá trị tại một vị trí sẽ thu được dãy $1,1,2$.
- Dãy $1,2,1,2$. Ví dụ, khi $H_2>H_4>H_1>H_3$, ta có $A_1=1,A_2=2,A_3=1,A_4=2$. Khi $H_2>H_1>H_4>H_3$, ta cũng có $A_1=1,A_2=2,A_3=1,A_4=2$.
- Dãy $1,1,2,3$. Ví dụ, khi $H_4>H_3>H_1>H_2$, ta có $A_1=1,A_2=1,A_3=2,A_4=3$.
- Dãy $1,1,2,1$. Ví dụ, khi $H_3>H_1>H_2>H_4$, ta có $A_1=1,A_2=1,A_3=2,A_4=1$.
- Dãy $1,1,2,2$. Ví dụ, khi $H_3>H_4>H_1>H_2$, ta có $A_1=1,A_2=1,A_3=2,A_4=2$.
- Dãy $1,1,1,2$. Ví dụ, khi $H_4>H_1>H_2>H_3$, ta có $A_1=1,A_2=1,A_3=1,A_4=2$.
Dữ liệu vào 2
8 1 1 2 1 2 3 1
Dữ liệu ra 2
15