ビルの飾りつけ 3

## JOISC2015 Day2T1 建筑装饰3 ### 题目描述 给定一个长度为$N-1$的正整数序列$B_i$，现在你可以在序列$B_i$的任意一个位置插入一个任意正整数，得到一个长度为$N$的序列$A_i$。 你需要求出满足以下条件的本质不同的序列$A_i$的数量： 存在一个长度为$N$的正整数序列$h_i$，满足$\forall 1 \leq i \neq j \leq N , h_i \neq h_j$，且$\forall i \in [1,N],$序列$h$中以位置$i$结尾的最长上升子序列长度为$A_i$。 ### 输入格式 第一行一个正整数$N$，接下来$N-1$行每行一个正整数$B_i$。 ### 输出格式 一行一个正整数表示本质不同的满足条件的序列数量。 ### 数据范围 $1 \leq N \leq 10^6$ $\forall i \in [1,N-1] , 1 \leq B_i \leq N$ ### 样例 #### 样例输入1 ``` 4 1 1 2 ``` #### 样例输出1 ``` 5 ``` ### 样例输入2 ``` 8 1 1 2 1 2 3 1 ``` ### 样例输出2 ``` 15 ```

[problemUrl]: https://atcoder.jp/contests/joisc2015/tasks/joisc2015_e