まず折り目の構造を観察します。奇数番目の折り目のみを取り出すと、山折り谷折りが VMVM... と続いています。偶数番目の折り目のみを取り出すと再帰的にこの構造になっています。別の表現をすると、折り目を番号の \(2\) 進数表記の \(1\) である最下位 bit でグループ分けしたとき、それぞれ VMVM... となっています。これは数学的帰納法などで証明することができます。この構造を解法に利用します。

\(f(a, k)\) を列 \(a = (a_1, a_2, \dots ,a_m)\) について \(i \bmod 4 = k\) を満たす \(i\) をとったときの問題の答えとします。

\(k = 0, 2\) であるときは \(a\) の奇数要素 、\(k = 1,3\) であるときは \(a\) の偶数要素については答えへの寄与が一意に定まります。なぜなら、そのような要素 \(a_x\) について \(a_x + i\) 番目の折り目の種類は \(i \bmod 4\) のみに依存するからです。

寄与が定まっていない要素、つまり \(k = 0, 2\) であるときは偶数要素、 \(k = 1, 3\) であるときは奇数要素を取り出して \(2\) で割った (切り捨て) 列を \(b = (b_1, b_2, \dots ,b_l)\) とします。寄与が定まっていない要素の寄与は \(\max (f(b, \lceil \frac{k}{2} \rceil), f(b, \lceil \frac{k}{2} \rceil + 2))\) と再帰的に数えることができます。これは上で述べた折り目自体の再帰的な構造、また \(100\) 回の操作が制約に対して十分大きいことによります。

\(A\) のある要素から由来する要素が再帰の間 \(a\) に出現する回数が高々 \(\log_2 \max A\) であることから、この解法は十分高速です。適切に実装をすれば計算量は \(O(N \log \max A)\) となります。