\(Q\) が固定された場合の問題を考えます．

\(Q_N\neq N\) のとき，答えは明らかに \(0\) です．\(Q_N=N\) の場合，答えは，\(Q_i = \max(Q_1,\ldots,Q_i)\) を満たすような \(i\ (2\leq i \leq N)\) の個数を \(k\) として \(2^k\) であることが \(Q_N\) の操作前の位置に着目して \(N\) についての数学的帰納法を回すことで証明できます．

\(Q\) が動く場合を考えます．\(Q\) を先頭の項から決めていくとき，最大値を更新するたびに \(2\) を乗じることにすれば，必要な情報はこれまで決めた \(Q\) の最大値のみです．

dp[先頭 \(i\) 項目を決めた]\([\max(Q_1,\ldots,Q_i)=j\)] = 答えの総和

と定義した動的計画法により \(\mathrm{O}(N^3)\) でこの問題を解くことができます．この動的計画法は累積和により \(\mathrm{O}(N^2)\) に高速化できます．