Cartesian Tree を作り、木DPを行います。頂点 \(i\) を根とした部分木における順列の個数 \(dp[i]\) を考えます。 各頂点について、自分より左右の位置それぞれに祖先が存在するかによって分けて考えます。

操作を逆から考えると、頂点 \(i\) を選べるのは両隣どちらかにそれより大きい値が存在するときです。

頂点 \(i\) の左右に祖先が存在する場合

\(dp[i]\) を、頂点 \(i\) を根とした部分木において、両端に十分大きな値があるとしたときの順列の個数とします。

頂点 \(i\) を選ぶまでは、左子孫と右子孫どちらか一方のみからしか選ぶことができません。なぜなら、頂点 \(i\) を選ぶときに両隣どちらかにそれより大きい値が存在する必要があるからです。

逆に、それ以外の選び方は可能です。 頂点 \(i\) を選ぶ前、つまり左子孫と右子孫のどちらか一方のみから選ぶ場合、その子孫内での並べ方を自由に行えます。 頂点 \(i\) を選んだ後であれば、左子孫と右子孫それぞれで干渉しません。

そのような選び方(を求めるための係数)は、左右の子孫の個数をそれぞれ \(L,R\) として、\(\binom {L+R}L + \binom{L+R}{L-1} + \binom {L+R}{L+1}\) それぞれ \(i\) が最初の場合、\(L\) が最初の場合、\(R\) が最初の場合の数です。 \(dp[i]\) はこの係数に \(dp[l], dp[r]\) を掛け合わせれば良いです。

頂点 \(i\) の左右のどちらか一方に祖先が存在しない場合

祖先が左にのみ存在する場合を考えます。(右の場合も同様です。)

\(dp[i]\) を、頂点 \(i\) を根とした部分木において、左端に十分大きな値があるとしたときの順列の個数とします。

頂点 \(i\) を選ぶまでは、右子孫のみからしか選ぶことができません。なぜなら、頂点 \(i\) を選ぶときに左にそれより大きい値が存在する必要があるからです。

逆に、それ以外の選び方は可能です。 頂点 \(i\) を選ぶ前、右子孫のみから選ぶ場合、その子孫内での並べ方を自由に行えます。 頂点 \(i\) を選んだ後であれば、左子孫と右子孫それぞれで干渉しません。

係数は\(\binom {L+R+1}{L+1}\) であり、 これに \(dp[l], dp[r]\) を掛け合わせれば良いです。

左右のどちらにも祖先が存在しない場合、つまり頂点 \(N\) については、\(N\) を必ず最初に選ぶと考えれば係数は \(\binom{L+R}{L}\) です。

全体で \(O(N)\) で計算できます。