\(17\leq N\) に対する解法です。

まず、 \(N=5n\) として、以下の操作をすることで \(2n+2\) 回で達成できます。

• \(1\leq i\leq n-1\) 回目は \(A[i+1+jn]\leftarrow \text{concat}(A[i+jn],A[i+jn+1])\) を \(j=0,1,2,3\) に対して行う。

• \(n\leq i\leq n+3\) 回目は \(A[n(i-n)+1+n]\leftarrow \text{concat}(A[n(i-n)+1],A[n(i-n)+1+n])\) を行う。

• \(n+4\leq i \leq 2n+2\) 回目は \(a=i-(n+3)\) として、 \(A[jn+a+1]\leftarrow \text{concat}(A[jn+a],A[jn+a+1])\) を \(j=1,2,3,4\) に対して行う。

イメージとしては \(5\) 分割して、前半 \(4\) つに対して累積和を取った後、先頭のみ累積和を取って、最後に後半 \(4\) つに対して累積和を取るイメージです。

このやり方は、真ん中の操作に無駄があります。(1回の操作で1つの \(\text{concat}\) しかしていないため)

\(5\) 分割したときの要素の数を \(X_{1},X_{2},..,X_{5}\) としたとき、最初のやり方では \(X_{1}=X_{2}=...=X_{5}\) としていますが、例えば、\(X_{1}=X_{2}=X_{3}+1=X_{4}+2\) とすることで真ん中の操作を別の操作と並列にすることができます。

このやり方をベースとして無駄な計算を減らせば最小回数を達成することができます。(雑でごめんなさい…)

実装例