Firstly, a few remarks: ~n~ is the number of vertices in a polygon. ~x \leftrightarrow y~ represents a diagonal with its endpoints in vertices ~x~ and ~y~. To avoid some edge cases, sides of the polygon are regarded as diagonals.

Basic observation is that removing a diagonal uniquely determines which diagonal must be added.

Let's focus on a particular, arbitrary triangulation that, without loss of generality, we are trying to transform into a fan triangulation at vertex ~1~.

Lemma 1. If ~d~ diagonals have an endpoint in vertex ~1~, number of operations needed is ~n-3-d~.

~n-3-d~ is obviously a lower bound. If ~n = d-3~, we are done. Otherwise, there exists a vertex ~x~ such that diagonal ~1 \leftrightarrow x~ is not present. Let ~lo~ be the largest integer less than ~x~ such that there exists a diagonal ~1 \leftrightarrow lo~. Observe that such an integer exists as diagonal ~1 \leftrightarrow 2~ exists. Similarly, let ~hi~ be the smallest integer larger than ~x~ such that diagonal ~1 \leftrightarrow hi~ exists. Observe that such an integer exists as diagonal ~1 \leftrightarrow n~ exists. Claim is that diagonal ~lo \leftrightarrow hi~ exists. Namely, it is known that every triangulation of every polygon has at least two "ears", where an "ear" is a vertex if it is an endpoint of no diagonal. Now it is clear, by the way we defined numbers ~lo~ and ~hi~, that vertex ~1~ is an "ear" in a polygon with vertices ~1, lo, lo+1, \dots, hi-1, hi~. If a vertex is an "ear", there exists a diagonal between its neighbors, namely between ~lo~ and ~hi~. Let's look at diagonals from vertex ~lo~. Let ~mid~ be the largest integer less than ~hi~ such that diagonal ~lo \leftrightarrow mid~ exists. Such integer exists as ~lo < x < hi~ and diagonal ~lo \leftrightarrow lo+1~ exists. Analogously, there exists a diagonal ~mid \leftrightarrow hi~. Now it is clear that by removing diagonal ~lo \leftrightarrow hi~ we must add diagonal ~1 \leftrightarrow mid~, that is it is possible to increase number of diagonals with one of its endpoints in vertex ~1~ and we are done.

Let ~lo~, ~hi~ and ~mid~ be integers from previous paragraph. By "fixing" diagonal ~1 \leftrightarrow mid~, (at most) two new intervals were created, namely ~[lo, mid]~ and ~[mid, hi]~ that have the same characteristics of an interval ~[lo, hi]~, such as having a unique diagonal that is possible to "fix". Observations so far motivate the definition of the following graph: vertices are diagonals that need to be "fixed" together with a dummy vertex. At the start, some diagonals are immediately "fixable" so we add a directed edge from dummy vertex to these diagonals. When we "fix" one diagonal, we add a directed edge to new diagonals that become "fixable". We created a directed acyclic graph of dependencies between diagonals. If there is a path from vertex ~a~ to vertex ~b~, it means that diagonal ~a~ must be "fixed" before diagonal ~b~. Also, the graph is a rooted tree with root being the dummy vertex and we are looking for the number of topological orders of this tree. Next lemma proves useful with calculating this number:

Lemma 2. Given a rooted tree with ~n~ vertices where ~i~-th vertex has its subtree size ~sz_i~, number of topological order is ~\dfrac{n!}{\prod_{i=1}^n sz_i}~.

This is a well-known fact, and as such, left as an exercise for the reader. For further information refer to the following Codeforces blog: link.

To efficiently calculate the product in the denominator, let's take a step back. We associate a diagonal that must be removed with the diagonal that it "fixes". Using previous notation, we associate the diagonal ~1 \leftrightarrow mid~ with the diagonal ~lo \leftrightarrow hi~. But, by the way we chose vertices ~lo~ and ~hi~, every vertex between them does not have a diagonal with its endpoint in vertex ~1~ and every such vertex corresponds to a diagonal in the subtree of the diagonal ~1 \leftrightarrow mid~. Observing one diagonal ~x \leftrightarrow y~ (~x < y~), we see that it contributes to vertices ~x+1, x+2, \dots, y-2, y-1~ with a factor of ~\frac{1}{n-(y-x)-1}~, and to all other vertices (other than ~x~ and ~y~) with a factor of ~\frac{1}{y-x-1}~. If we use a segment tree that keeps a product of numbers in an interval, the operation of removing one and adding another diagonal is a few updates in a segment tree with complexity ~\mathcal{O}(\log n)~ if we precompute inverses. We calculate the number of diagonals from each vertex explicitly and precompute needed factorials. Total time complexity is ~\mathcal{O}(n + q \log n)~ or ~\mathcal{O}((n+q) \log n)~ depending on complexity of the precomputation of inverses.