題解

首先，我們嘗試在給定高度排列的情況下，用一種簡潔的方式求出最后還剩余的柱子的坐標是哪些。容易想到如下方式：

• 設第 \(i(1\leq i \leq 2n)\) 個柱子的高度為 \(h_i\)，然后設一個標記數組 \(f_{0..n}\)，初始時 \(f\) 沒有元素被標記。考慮按照柱子編號從大到小插入柱子。假設當前插入的柱子是 \(i\)，則找到一個最大的 \(j\)，使得 \(j\leq i\) 且 \(f_j\) 沒有被標記；如果 \(j=0\)，那么該柱子最終沒了，否則，該柱子是最后還剩余的柱子之一，并將 \(f_j\) 標記。

于是，我們發現只有當 \(f_1,f_2,\cdots,f_{h_i}\) 都被標記時，該柱子最終會消失。

接下來我們來考慮如何計數。

首先，同一個高度會出現兩次，而且沒有區別，比較棘手，我們可以將這兩個值相同的高度看做不同的，并在最后給答案乘上 \(\frac{1}{2^n}\) 去重。

然后，我們設 \(F_i\) 表示使用 \(i+1\) 個柱子標記連續的長度為 \(i+1\) 的一段區間，并要求在使用前 \(i\) 個柱子時，該區間的第一個元素還沒被標記。這可以通過簡單的動態規劃得到。后面的計算過程會使用 \(F_i\)。

定義 \(g_{i,j}\) 表示當前加入了第 \(i,i+1,\cdots, 2n\) 個柱子，且 \(f_1,\cdots,f_j\) 被標記，且 \(f_{j+1}\) 沒有被標記，且不考慮除了與標記這些位置相關的柱子以外的柱子，在這種情況下的方案數。接下來我們考慮 \(g_{i+1,j}\) 會對哪些值做貢獻：

• 設 \(i+1\) 號到 \(2n\) 號柱子中有 \(cnt_0\) 個最終消失，有 \(cnt_1\) 個最終留下。
• 若 \(i\) 號柱子最終消失：則該柱子的高度必然小于等于 \(j\)，在小于等于 \(j\) 的還沒被使用的高度中任選一個，由于前 \(j\) 種高度總共有 \(2j\) 個選法，為了標記 \(1..j\)，消耗了 \(j\) 個，為了使之前的 \(cnt_0\) 個柱子消失，消耗了 \(cnt_0\) 個，所以還剩 \(j-cnt_0\) 個選法，故 \(g_{i,j}+=(j-cnt_0)g_{i+1,j}\)。
• 否則：
  1. 如果當前柱子沒有使 \(f_{j+1}\) 被標記，那么我們把給當前柱子取高度的問題放到之后解決，這里直接 \(g_{i,j}+=g_{i+1,j}\)。
  2. 如果當前柱子使 \(f_{j+1..j+k+1}(0\leq k\leq cnt_1-j)\) 被標記（注意我們還有 \(cnt_1-j\) 個柱子還沒有取高度），那么我們需要在給當前柱子取高度的同時從還沒有取高度的 \(cnt_1-j\) 個柱子里選 \(k\) 個取高度，使得前面的條件滿足，于是就有 \(g_{i,j+k+1}+=\binom{cnt_1-j}{k}F_kg_{i+1,j}\)。

最后得到的 \(\frac{1}{2^n}g_{1,n}\) 就是答案了。

代碼

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outv(x) cerr<<#x" = "<<x<<"  "
#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
	For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
void ckmax(int &x,int y){
	if (x<y)
		x=y;
}
void ckmin(int &x,int y){
	if (x>y)
		x=y;
}
const int N=605;
int n;
int a[N*2];
int C[N][N],f[N][N],F[N],g[N*2+1][N];
int main(){
	n=read();
	For(i,1,n)
		a[read()]=1;
	For(i,0,n){
		C[i][0]=1;
		For(j,1,i)
			C[i][j]=Add(C[i-1][j-1]+C[i-1][j]);
	}
	f[0][0]=1;
	For(i,1,n)
		For(j,0,i-1){
			int v=f[i-1][j];
			if (!v)
				continue;
			Add(f[i][j],v);
			if (j+1<=i)
				Add(f[i][j+1],(LL)v*(j+1)*2%mod);
			if (j+2<=i)
				Add(f[i][j+2],(LL)v*(j+1)*(j+2)%mod);
		}
	For(i,0,n-1)
		F[i]=(LL)f[i][i]*(i+2)%mod;
	g[n*2+1][0]=1;
	int cnt0=0,cnt1=0;
	Fod(i,n*2,1){
		For(j,0,n){
			int v=g[i+1][j];
			if (!v)
				continue;
			int rp0=j-cnt0;
			int r1=cnt1-j;
			if (a[i]==0)
				g[i][j]=((LL)v*rp0+g[i][j])%mod;
			else {
				Add(g[i][j],v);
				For(k,0,r1)
					g[i][j+k+1]=((LL)v*F[k]%mod*C[r1][k]+g[i][j+k+1])%mod;
			}
		}
		if (a[i]==0)
			cnt0++;
		else
			cnt1++;
	}
	int ans=(LL)g[1][n]*Pow(2,mod-1-n)%mod;
	cout<<ans<<endl;
	return 0;
}