链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
已知一朵樱花有 n 枚花瓣，每一枚花瓣各不相同。将它们用一个长为 n 的排列编号。
我们根据一朵樱花的编号来认定它的特征：
每一个排列均具有两组特征码 fa，fb。其中，fai 表示排列 p 中第 1 个到第 i 个数的 MEX（前缀 MEX），fbi 表示排列 p 中第 i 个到第 n 个数的 MEX（后缀 MEX）。fa 由 fa1,fa2,⋯ ,fan 组成，fb 由 fb1,fb2,⋯ ,fbn 组成。如果存在两个排列的特征码 fa ，fb 均完全相同，那么我们就认为它们具有相同的特征。
现在，在贵树的手中有一朵樱花，他希望你求出有多少个排列和当前这个樱花的排列特征相同？
由于结果可能很大，所以你的答案需要对 109+710^9+7109+7 取模。
输入描述:
第一行输入一个整数 n(1≤n≤2×105)。 第二行输入 n 个整数，输入一个排列 p1,p2,⋯ ,pn(0≤pi<n,1≤i≤n)，表示贵树手里的樱花的特征。 保证 p1,p2,⋯ ,pn 是一个排列。
输出描述:
输出一个整数，代表有多少个排列和该排列特征相同（包括原排列本身），答案对 10^9+7 取模。
示例1
输入
5 3 1 0 4 2
输出
1
示例2
输入
7 0 6 5 4 3 2 1
输出
120
备注:
长为 n 的排列指一个长为 n 的序列，其中 0,1,⋯ ,n−1 均出现且仅出现 1 次。例如，(0,3,2,1,4) 是一个长为 5 的排列而 (1,2,4) 不是排列。
MEX 表示的是一个序列中没有出现的最小的自然数。例如，MEX(1,2,3,4,5)=0,MEX(0,1,2,3,3,5,6,7)=4。
解析：
B[i]：表示记录数字 i 在序列中的位置
left：记录前 i 小的数字的最小位置
right：记录前 i 小的数的最大位置
数字 i 可放在位置 left~right 之间，但由于前面已经有了 i-1 个确定位置的数，应次数字实际上可以放置的位置数量是 （right-left+1）-（i-1）.
这里的前 i-1 个数字一定会在 left~right 之间，因为如果前面的数字位置是一定的，那么由于left=min（left，B[j]）,right=max(right,B[j])，所以 left~right 之间一定包含 j 的位置；如果数字 j 的位置是不确定的，那么数字 j 也一定是在 left~right 之间选择位置。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f;
const LL Mod = 1e9 + 7;
const int N = 2e5 + 10, M = 4e5 + 10, P = 110;
int n;
int B[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
B[a+1] = i;
}
int left = n + 1, right = 0;
LL ret = 1;
for (int i = 1; i <= n; i++) {
left = min(left, B[i]), right = max(right, B[i]);
if (B[i] != left && B[i] != right) {
(ret *= (right - left + 1) - (i - 1)) %= Mod;
}
}
cout << ret << endl;
return 0;
}
