let mx[i] = largest vertice on the path ($$$i, i + 1$$$).

mn[i] = smallest vertice on the path ($$$i, i + 1$$$).

calculate number of pairs ($$$l < r$$$) such that $$$r - l$$$ = max(mx[ $$$l$$$ ..($$$r - 1$$$)]) — min(mn[ $$$l$$$ ..($$$r - 1$$$)]);

Someone already replied but here is my incoherent solution:

Let us iterate over the smallest node $$$u$$$ in a valid subgraph in decreasing order.

Define $$$f(u, v), u \leq v $$$ to be a boolean variable which indicates whether the set of nodes from $$$u$$$ to $$$v$$$ form a connected subgraph. Let's assume that we know all $$$v$$$ such that $$$f(u + 1, v) = 1$$$. Now, we want to find every node $$$w : f(u, w) = 1$$$.

Firstly, let's find the maximum node $$$mx$$$ on the path from $$$u$$$ to $$$u + 1$$$. Notice that for all $$$v < mx : f(u, v) = 0$$$. Further, for all $$$v \geq mx, f(u + 1, v) = 1 \implies f(u, v) = 1$$$.

Now, we will also have some $$$v \geq mx : f(u + 1, v) = 0, f(u, v) = 1$$$. For the sake of brevity, we define a set $$$S$$$ which contains all such $$$v$$$. Finding $$$S$$$ efficiently is the crux of the problem.

We make the following observations:

1. For every $$$v \in S$$$, $$$v \geq max(w) : f(u + 1, w) = 1$$$.
2. If $$$f(u + 1, v) = 1$$$, and $$$f(u, v) = 0$$$, then $$$f(w, v) = 0 \forall (w \leq u)$$$.

Thereafter, we find the answer in the following manner:

1. Iterate over $$$u$$$ in decreasing order, and maintain set $$$P$$$, which contains all $$$v : f(u, v) = 1$$$.
2. Each element is inserted and deleted atmost once from this set due to observation 1.
3. How to find $$$P$$$ for a particular $$$u$$$ assuming that $$$P$$$ currently contains the relevant nodes for $$$u + 1$$$? It's kinda hard to explain in text without being too long: We will be maintaining connected components of all nodes $$$\geq u$$$. When at $$$u$$$, we will delete all nodes $$$< mx$$$ from $$$P$$$, and then find greatest $$$x$$$ such that all nodes from $$$u$$$ to $$$x$$$ are in the connected component of $$$u$$$. Parallely, maintain another dsu and incrementally add nodes from $$$max(P) + 1$$$ to $$$x$$$. Whenever the node you add results in there being only connected cc containing all nodes from $$$u$$$ to that node, add that node to $$$P$$$.

This gives us a $$$O(n \log(n))$$$ solution.