In fact, the operation performed in the problem is exactly same as traversing Stern–Brocot tree.
Here, let us define the Stern–Brocot tree as follows:

• The root node is a segment \([0/1,1/0]\).
• Each node \([a/b,c/d]\) has the following children nodes:
  • \([a/b,(a+c)/(b+d)]\)
  • \([(a+c)/(b+d),c/d]\)

It is known that we can traverse all irreducible fractions in the sorted order. Therefore, “an integer pair \((p,q)\) may be inserted in \(A\)” \(\leftrightarrow\) “\(p\) and \(q\) are coprime.”

Let us call the following operation on each node a node operation:

• An operation against node \([a/b,c/d]\) can be performed if the sequence \(A\) in the original problem contains both \((a,b)\) and \((c,d)\).
• Performing a node operation on this node inserts \((a+c,b+d)\) to \(A\).
  • Now you can perform a node operation on nodes \([a/b,(a+c)/(b+d)]\) and \([(a+c)/(b+d),c/d]\).

Here, let us rephrase the problem as follows:
Find the sum over all the nodes of the answer to the following question: “how many subarray \(S_{l,r}\) requires the node operation against the node?”

For a fixed \(T:=S_{l,r}\), whether the node operation should be performed on the node \([a/b,c/d]\) can be determined by checking if there is an integer pair \((p,q)\) contained in \(T\) such that \(a/b < p/q < c/d\). (Here, we temporarily ignore the case where \(q=0\).)
Conversely, from the positions of the elements such that \(a/b < p/q < c/d\), we can count \(S_{l,r}\) on which we need to perform the node operation.
For example, when \(S=((3,5),(1,3),(2,1),(2,3))\), the subarrays that we need to perform a node operation on are the \(7\) subarrays that contains either the leftmost or rightmost elements.
Also, by the construction of the Stern-Brocot tree, it seems that we can solve the problem by first dividing the elements of \(S\) to left or right while diving into the tree, and then traversing backward while doing “merge technique” trick.

But there is an obstacle: in order to insert \((10^9,1)\), we need to perform at least \(10^9\) operations on \(A\). That’s why we need a fast way to descend and climb the Stern-Brocot tree.

So let us consider constructing the only needed part of Stern-Brocot tree.
For example, if a segment \([a/b,c/d]\) only contains elements near \(c/d\), we will be able to descend as \([(a+c)/(b+d),c/d],[(a+2c)/(b+2d),c/d],\dots\) consecutively. Indeed,w e can determine an integer \(k\) appropriately with binary search and dive from \([a/b,c/d]\) down to \([(a+kc)/(b+kd),c/d]\) at once as long as the elements are divided into left and right.
Here, if \(N=1\), then we can show that it is sufficient to perform the procedure above \(O(\log( \max(a_i,b_i) ))\) times to descend the Stern-Brocot tree.

Overall, the problem can be solved with a complexity of about \(O(N (\log N)^2 \log \max(a_i,b_i))\).

Sample code (C++)