#2998. 「JOISC 2015 Day2」Building 3

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Chiaki

题目描述

译自 JOISC 2015 Day2 T1「Building 3」。

给出一个长度为 N - 1 的序列 B_1, B_2, \dots, B_{N-1} ,求出有多少长度为 N 序列 A_1, A_2, \dots, A_N 满足:

  • A_1, A_2, \dots, A_N 删掉其中一个数后和 B_1, B_2, \dots, B_{N-1} 一样;
  • 存在一个长度为 N 的排列 H_1, H_2, \dots, H_N ,使得 A_i 是以 H_i 为结尾的最长递增子序列的长度。

输入格式

第一行包含一个整数 N ,表示序列的长度。

接下来 N - 1 行,第 j ( 1 \le j \le N - 1 ) 行包含一个整数 B_j ,含义如题所述。

输出格式

输出一个整数,表示满足条件的 A_1, A_2, \dots, A_N 的个数。

样例

样例输入 1

4
1
1
2

样例输出 1

5

样例解释 1

总共有 5 个满足条件的序列:

  • 1, 2, 1, 2 H_2 > H_4 > H_1 > H_3 或者 H_2 > H_1 > H_4 > H_3
  • 1, 1, 2, 3 H_4 > H_3 > H_1 > H_2
  • 1, 1, 2, 1 H_3 > H_1 > H_2 > H_4
  • 1, 1, 2, 2 H_3 > H_4 > H_1 > H_2
  • 1, 1, 1, 2 H_4 > H_1 > H_2 > H_3

样例输入 2

8
1
1
2
1
2
3
1

样例输出 2

15

数据范围与提示

对于全部数据,满足 2 \le N \le 10^6, 1 \le B_j \le N

本题共有 3 个子任务。每个子任务的分数和附加限制如下:

Subtask 附加限制 分数
1 N \le 8 10
2 N \le 300 30
3 无附加限制 60