\(i\) 番目の折れ線が山折り \(\Leftrightarrow\) \(i = a2^b\) \((a \text{: 奇数})\) としたとき、\(a \bmod 4 = 3\)

であることが再帰的構造よりわかります。

よって、

\(i + A_k\) 番目が山折り \(\Leftrightarrow\) \(\exist t \), \(i + A_k = 3 \times 2^t \bmod 2^{t +2}\)

と表現することができます。これはつまり、\(i\) の末尾 \(t\) 桁が \(s\) である、という条件です。 これらの条件は \(2\) で割り切れる回数を考えると同じ \(k\) に対して重複することはありません。よって、すべての \(k, t\) についてこれらの条件をすべて列挙したときに、最も多くの条件を満たすようにできる \(i\) を取る問題になりますが、これは trie 木で簡単に処理することができます。

よって、全体で \(O(N \log A)\) で解くことができました。