計算式から以下のことが分かります。

• \(A_j=0, i<j\)のとき\(f(i,j)=1\)
• \(A_j=1, j\geq2, i<j\)のとき\(f(i,j)\)と\(f(i,j-1)\)のどちらか一方のみ\(1\)、つまり\(f(i,j)+f(i,j-1)=1\)

これらより、さらに以下のことが分かります。

• \(A_j=0\)のとき\(\sum_{1\leq i\leq j}f(i,j)=j-1\)
• \(A_j=1\)のとき\(\sum_{1\leq i\leq j}(f(i,j-1)+f(i,j))=j\)（ただし\(i>j\)のとき\(f(i,j)=0\)とする。）

したがって以下の方法で答えを得ることができます。

はじめ、\(ans=0\)とする。\(i=1,2,\dots ,N\)の降順に以下の操作を行う。

• \(A_i=0\)の場合
  • \(ans\)に\(i-1\)を加算する。
• \(A_i=1\)の場合
  • \(ans\)に\(i\)を加算する。
  • さらに\(i\geq2\)なら\(A_{i-1}\)を\(2\)に変更する。
• \(A_i=2\)の場合
  • 何もしない。

操作終了後の\(ans\)が求める答えである。