左端および右端から見える建物の個数をそれぞれ \(C_0,C_N\) とします.

建物の高さの列 \(H\) の（区間の最大値を部分木の根とする）Cartesian Tree が \(C\) を定めます. 逆に，\(C\) から Cartesian Tree を復元することを考えましょう.

\(k\) 個の建物からなる列から，\(k+1\) 個の「隙間」から見える建物の個数を表す長さ \(k+1\) の数列が得られます. 空列から始めて，建物を高さの高い順に挿入し，そのたびに各隙間から見える建物の個数の列を記録するものとし，その逆操作を考えます. 最も高さの低い建物に注目します. この建物のすぐ左およびすぐ右から見える建物の個数は等しいです. この個数を \(x\) とします. その建物を取り除いたときに，その隙間から見える建物の個数は \(x-1\) になります.

このことから，\(C=(C_0,C_1,\dots, C_{N})\) から Cartesian Tree が復元できるための必要十分条件は次のように与えられます.

• \(C\) に対して以下の操作を繰り返すことで，\(C=(0)\) にできる.
  • \(C\) に含まれる最大値 \(x\) であって \(x\) どうしが隣りあうもののうち最も左にあるものを見つけ，列からその \(2\) つの \(x\) を削除し，その位置に \(x-1\) を挿入する.

この構成自体が Cartesian Tree を与えます. 実装の際は最大値をマージするようなことをしなくとも，\(C\) を前から見て stack で処理することができます. また，Cartesian Tree \(T\) が与えられたとき，それを実際に Cartesian Tree として与えるような \(H\) の個数は，\(T\) の各頂点 \(v\) に対して \(v\) を根とする部分木の大きさを \(S_v\) としたときに

\[ \dfrac{N!}{\prod_{v}S_v} \]

と表せることが知られています. 以上で，\(C_0,C_N\) も与えられた場合はこの問題を解くことができました. Cartesian Tree を復元できない場合に注意してください. この場合の答えは \(0\) です.

実は，\(C_0,C_N\) の候補は高々 \(2\) 通りに絞ることができます. Cartesian Tree を復元する操作には \(\sum_{x\in C}2^{-x}=1\) という不変量が存在します. したがって，\(1-\sum_{i=1}^{N-1}2^{-C_i}\) という量を二進表記したときに，立っている bit が \(2\) つなら \(2\) 通り，\(1\) つなら \(1\) 通りの候補を調べればよいです. \(C_0=C_N\) の真偽に注意してください. \(2\) つの異なる Cartesian Tree が得られる可能性があります.

以上の解法は \(O(N)\) time で動作します.