実は、この問題で行われる操作は、 Stern–Brocot tree を辿ることそのものです。
今回扱う Stern–Brocot tree を以下のように定めます。

• 根ノードは区間 \([0/1,1/0]\) である。
• ノード \([a/b,c/d]\) の下には、以下の子ノードがある。
  • \([a/b,(a+c)/(b+d)]\)
  • \([(a+c)/(b+d),c/d]\)

これにより、全ての既約分数を sorted な順に辿っていくことができることが知られています。なので、「整数組 \((p,q)\) が \(A\) に追加されうる」 \(\leftrightarrow\) 「 \(p,q\) が互いに素」です。

各ノードに対して以下を行うことを ノード操作 と呼びましょう。

• ノード \([a/b,c/d]\) に対しての操作は、元の問題の数列 \(A\) に \((a,b),(c,d)\) が双方ある時に行える。
• このノードにノード操作を行うと、 \((a+c,b+d)\) が \(A\) に追加される。
  • これ以降、ノード \([a/b,(a+c)/(b+d)],[(a+c)/(b+d),c/d]\) に対するノード操作が行えるようになる。

ここで、問題を以下のように言い換えましょう。
「全てのノードについて、そのノード操作を行うべき区間 \(S_{l,r}\) はいくつありますか?」という質問の答えを、全てのノードについて足し合わせる。

\(S_{l,r}\) をひとつ決め打ってそれを \(T\) とした時にノード \([a/b,c/d]\) でノード操作を行うべきかどうかは、 \(T\) に含まれる整数組 \((p,q)\) であって \(a/b < p/q < c/d\) なるものが含まれるかどうかで判定できます。( \(q=0\) の場合は一旦無視しています)
逆に、 \(a/b < p/q < c/d\) なる要素がどこにあるかという情報から、そのノード操作を行うべき \(S_{l,r}\) がいくつあるかも求められます。
例えば、 \(S=((3,5),(1,3),(2,1),(2,3))\) である場合に、ノード \([1/2,1/1]\) でノード操作を行うべきような部分列は両端の要素のいずれかを含むような \(7\) 個の部分列です。
また、 Stern-Brocot tree の作りから、 \(S\) の要素をどんどん左か右に分割していき木を上から下に辿っていった後、木を下から上に辿ってマージテクを行えばうまく問題全体を解けそうです。

ここで障壁があります。例えば \((10^9,1)\) を追加するためには \(A\) に最低 \(10^9\) 回の操作を行う必要があります。なので、高速に Stern-Brocot tree を登り降りする方策を考えねばなりません。

そこで、 Stern-Brocot tree のうち必要な部分だけ作ることを考えましょう。
例えば、区間 \([a/b,c/d]\) 内に \(c/d\) に近い要素しか含まれない場合、 \([a/b,c/d]\) から \([(a+c)/(b+d),c/d],[(a+2c)/(b+2d),c/d],\dots\) のように連続で下っていけそうです。実際に、ある整数 \(k\) を二分探索などを用いて適切に決めて、 \([a/b,c/d]\) から \([(a+kc)/(b+kd),c/d]\) まで、要素が左右のノードに分かれない範囲で一気に下っていくことができます。
なお、もし \(N=1\) であった場合は、上の手続きを \(O(\log( \max(a_i,b_i) ))\) 回行えば Stern-Brocot tree を下るには十分であることが示せます。

全体としては、 \(O(N (\log N)^2 \log \max(a_i,b_i))\) といった計算量でこの問題に正解することができます。

実装例(C++)