细节题，转移并不难，难点在于状态的设计。

设 $h$ 中出现过不同的数的数量为 $c$，原问题等价于把这 $c$ 个数放在 $n$ 个位置上，有些位置空着不放，且 $i$ 和放 $a_i$ 的位置距离不超过 $1$ 的方案数，最后再乘上 $(n-c)!$ 就是答案了。

容易观察到有如下性质：

• 如果 $a_{i-2}=a_i$，则 $a_i$ 必然放在 $i-1$ 这个位置上；如果 $a_{i-1}=a_i$，则 $a_i$ 必然放在 $i-1$ 或者 $i$。
• 如果 $j<i-1$，则最终 $a_j$ 必然不会放在 $a_i$ 的后面。

那么就可以考虑 dp，设只考虑前 $i$ 个的方案数为 $f_{i,0/1/2/3/4}$，有如下几种情况：

1. $a_i$ 放在位置 $i-1$ 上，且 $a_{i-1}$ 不在 $a_i$ 的后面，这种情况的方案数记为 $f_{i,0}$；
2. $a_i$ 放在位置 $i-1$ 上，且 $a_{i-1}$ 放在 $i$ 上，记为 $f_{i,1}$；
3. $a_i$ 放在 $i$ 上，记为 $f_{i,2}$；
4. $a_i$ 放在 $i+1$ 上，且 $a_{i-1}$ 放在 $i$ 上，记为 $f_{i,3}$；
5. $a_i$ 放在 $i+1$ 上，且 $a_{i-1}$ 不放在 $i$ 上，记为 $f_{i,4}$（拆出 $f_{i,3}$ 和 $f_{i,4}$ 是为了能够转移，这个一会儿再说）。

那么就可以开始转移了，这个要根据 $a_i$ 的位置和数量分类讨论来转移：

1. $a_{i-2}=a_{i-1}=a_i$，显然 $a_i$ 只能要放在 $i-1$，转移 $f_{i,0}=f_{i-1,2}$；
2. $a_{i-2} = a_i$，且 $a_{i-1} \ne a_i$，那么 $a_i$ 还是只能放在 $i-1$，转移 $f_{i,0}=f_{i-1,1}$， $f_{i,1}=f_{i-1,3}$；
3. $a_i =a_{i-1}$ 且 $a_{i-1} \ne a_{i-2}$，转移 $f_{i,0}=f_{i-1,2}$， $f_{i,2}=f_{i-1,3}+f_{i-1,4}$；
4. $a_i \ne a_{i-1}$ 且 $a_i \ne a_{i-2}$，转移 $f_{i,0}=f_{i-1,0}$， $f_{i,1}=f_{i-1,4}$， $f_{i,2}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}$， $f_{i,3}=f_{i-1,3}+f_{i-1,4}$， $f_{i,4}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}$。

最终答案 $(n-c)!(f_{n,0}+f_{n,1}+f_{n,2})$，最开始的时候特判一下无解的情况，那么这题就做完了，时间复杂度 $\mathcal O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,a[N],cnt[N],lst[N],f[N][5],sum,ans;
vector<int>vec[N];
void add(int &x,int v){
	x+=v;
	if(x>=mod) x-=mod;
}
void gg(){
	cout<<"0\n";
	exit(0);
}
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];
		if(!cnt[a[i]]) sum++;
		cnt[a[i]]++;
		vec[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(cnt[i]>3) gg();
		if(cnt[i]==3&&(vec[i][2]-vec[i][1]>1||vec[i][1]-vec[i][0]>1)) gg();
		if(cnt[i]==2&&vec[i][1]-vec[i][0]>2) gg();
	}
	f[1][2]=f[1][4]=1;
	for(int i=2;i<=n;i++)
		if(i>=3&&a[i-2]==a[i-1]&&a[i-1]==a[i]) f[i][0]=f[i-1][2];
		else if(i>=3&&a[i-2]==a[i]){
			f[i][0]=f[i-1][1];
			f[i][1]=f[i-1][3];
		}
		else if(a[i-1]==a[i]){
			f[i][0]=f[i-1][2];
			f[i][2]=f[i-1][3];add(f[i][2],f[i-1][4]);
		}
		else{
			f[i][0]=f[i-1][0];
			f[i][1]=f[i-1][4];
			f[i][2]=f[i-1][1];add(f[i][2],f[i-1][0]);add(f[i][2],f[i-1][2]);
			f[i][3]=f[i-1][3];add(f[i][3],f[i-1][4]);
			f[i][4]=f[i-1][0];add(f[i][4],f[i-1][1]);add(f[i][4],f[i-1][2]);
		}
	ans=f[n][0];add(ans,f[n][1]);add(ans,f[n][2]);
	for(int i=1;i<=n-sum;i++) ans=1ll*ans*i%mod;
	cout<<ans<<'\n';
    return 0;
}