\(r=1.01\) と書くことにします．

[1] 解法

まずは，自明な解法として次が考えられます．

• 集合 \(X_i\) を，\(a_1,\ldots,a_i\) の部分列の和全体の多重集合とする．
• \(X_{i+1}\) は，\(X_i\cup \{s+a_{i+1}\mid s\in X_i\}\) により求められる．

これで計算量 \(O(N\max |X_i|)\) という解法になります．しかしこれでは \(|X_i|\) が大きすぎるので，答の計算に不要な情報を適切に捨てて，保持するべき状態を減らしましょう．

次が成り立つことは簡単に分かります：\(0\leq s\leq t\leq rs\) ならば，任意の \(a>0\) に対して \(0\leq s+a\leq t+a\leq r(s+a)\)．

すると，\(X_i = \{s_1,s_2,\ldots\}\) （昇順）とし，\(L\leq R\) について \(s_L\leq s_R\leq r s_L\) が成り立つとき，\(s_{L+1},\ldots,s_{R-1}\) をすべて \(s_L\) に置き換えても答は変わらないことが分かります．このことは例えば残り操作回数に関する帰納法で簡単に証明できます．

常に \(X_i\) の要素の種類数をこの方法で可能な限り減らし，代わりに各要素の出現頻度を持つようにします．

ある時点での \(X_i\) に含まれる相異なる要素を \(x_1<x_2<\cdots\) とすれば，\(r x_i \leq x_{i+2}\) が成り立つようになるため，保持すべき要素の種類数は \(O(\log_r (\sum A_i))\) となります．

以上により本問題は計算量 \(O(N\log_r(\sum A_i))\) 時間で解くことができます．