Có \(N\) tòa nhà dọc đại lộ, đánh số từ sân bay đến nơi lưu trú; mọi chiều cao đôi một khác nhau. Chỉ có thể trang trí một dãy tòa nhà có chiều cao tăng nghiêm ngặt theo hướng từ sân bay.

Với mỗi \(i\), đặt \(A_i\) là số tòa nhà lớn nhất có thể chọn khi bắt buộc chọn tòa \(i\) và tòa \(i\) phải là tòa được chọn gần nơi lưu trú nhất. K đã nhận một dãy \(B_1,\ldots,B_{N-1}\) và cho rằng JOI đã bỏ quên đúng một phần tử của dãy \(A\). Hãy đếm số dãy giá trị khác nhau \(A_1,\ldots,A_N\) có thể sinh ra từ một cách gán các chiều cao đôi một khác nhau và trở thành \(B\) sau khi xóa một phần tử.

Dữ liệu vào

Dòng đầu chứa \(N\). Mỗi trong \(N-1\) dòng sau chứa \(B_j\).

Dữ liệu ra

In số dãy \(A\) thỏa mãn.

Ràng buộc

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le8\).
• Nhóm 2 (30 điểm): \(N\le300\).
• Nhóm 3 (60 điểm): không có ràng buộc bổ sung.

Ví dụ

4
1
1
2

5

8
1
1
2
1
2
3
1

15