Let S denote the total number of operations.

We divide the sequence of operations into two stages, where the second stage satisfies the following condition:

$$$\exists k \lt S\ s.t.\ \forall S \gt i \gt k, [l_{i}, r_{i}] \subset [l_{i + 1}, r_{i + 1}]$$$

It is evident that this stage must exist. We classify all preceding operations as Stage 1.

First, we make several observations:

Observation 1. At any point, if the length of an interval is 1, no solution exists.

Proof: Trivial.

Observation 2. At any point, if the current interval is a sub-interval of the previous one, no solution exists. Formally, if $$$\exists S \ge x \gt y \ge 1\ s.t.\ [l_x, r_x] \subseteq [l_y, r_y]$$$, there is no solution.

Proof: This results in a cycle.

Corollary: For the worst case Stage 2 must begin with an interval of length 2 and requires at most $$$n−2$$$ operations to reach $$$[1,n]$$$.

Observation 3. If there exists a k such that $$$[l_{k−1}​,r_{k−1}​] \subseteq [l_k​, r_k​]$$$, then for all $$$S \gt i \gt k$$$, $$$[l_{i−1}​,r_{i−1}​]⊆[l_i​,r_i​]$$$ holds. In other words, once an interval begins to "expand" outward, it will continue to expand indefinitely.

Proof: After expansion, the minimum value is non-increasing, and the maximum value is non-decreasing.

This implies that as soon as a single "expansion" occurs, the process immediately enters Stage 2.

Next, let us consider Stage 1. We are presented with the following problem: Given a segment of length n, we continuously place intervals upon it subject to the constraint that the current interval implies neither a subset nor a superset relationship with any previously placed interval. What is the maximum number of intervals that can be placed? (Note: We do not discuss the explicit construction of the corresponding array a here).

Clearly, the optimal strategy is to consistently place intervals of length 2. This allows for $$$n−1$$$ operations. Subsequently, an "expansion" must occur, triggering the transition to Stage 2. The first interval placed corresponds to the initial condition given in the problem, and the final interval placed acts as the first interval of Stage 2. Consequently, the maximum number of operations is $$$2n−4$$$.

For the case where $$$n=3, a=[2,3,1]$$$ and the initial operation is $$$f(1,2)$$$, this upper bound is achieved. Therefore, this result cannot be improved further.