简要思路

发掘性质：根据最长上升子序列的 dp 方程有 $f_i=\max_{j=1}^{i-1} f_j+1[a_j<a_i]$，所以插入在 $b_i,b_{i+1}$ 的数 $x$ 必须保证 $1\le x\le \max_{j=1}^{i}b_i+1$，记录 $mx_i=\max_{j=1}^{i}b_i$。

分情况考虑：

1.存在 $mx_i+2<b_{i+1}$，无解。

2.存在不止一个 $mx_i+2=b_{i+1}$，无解。

3.只有一个 $mx_i+2=b_{i+1}$，可以插入一个 $mx_i+1$ 以保证合法，但不一定一定要插到 $i$ 的前一位，统计 $i$ 前有多少个 $j$ 满足 $b_j=mx_i$，可以将 $mx_i+1$ 插到 $j$ 后面。

4.没有 $mx_i+2=b_{i+1}$。可以随便插，基本答案即为 $\sum_{i=1}^n mx_i+1$，但是在如果在 $b_i$ 左插入 $x=b_i$ 或在 $b_i$ 右插入 $x=b_i$，这两种方案得到的 $A$ 相同，会重复计算，所以答案在最后还要减去 $n$，再加上插到最前面一个 $1$ 的答案 $1$，最终答案为 $(\sum_{i=1}^n mx_i+1)-n+1$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],maxn[1000005],fl; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		maxn[i]=max(maxn[i-1],a[i]);
		if(maxn[i-1]+2<a[i]){
			cout<<0;
			return 0;
		}if(maxn[i-1]+2==a[i]){
			if(fl){
				cout<<0;
				return 0;
			}else fl=i;
		}
	}
	long long ans=0;
	if(fl){
		for(int i=0;i<fl;i++){
			if(maxn[i]==a[fl]-2)ans++;
		}
		cout<<ans;
		return 0;
	}
	for(int i=1;i<=n;i++){
		ans+=maxn[i]+1;
	}
	ans-=n;ans++;
	cout<<ans;
	return 0;
}