Exquisite Array

Let

$$d_i = |p_i - p_{i+1}| \qquad (1 \le i < n).$$

A subarray $p_l, p_{l+1}, \dots, p_r$ with $l < r$ is $k$-exquisite iff

$$\min(d_l, d_{l+1}, \dots, d_{r-1}) \ge k.$$

So the actual array values are mostly a distraction after we compute adjacent differences. Classic Codeforces move: reduce the problem to edges, and suddenly the scary statement is just wearing a fake mustache.

For a fixed $k$, call an edge position $i$ active if $d_i \ge k$. Then valid subarrays are exactly contiguous intervals of active edge positions.

If we have a maximal active block of $m$ consecutive edges, how many subarrays does it create? Any nonempty interval of edges inside that block corresponds to exactly one subarray of values. The number of nonempty intervals in a length-$m$ block is

$$1 + 2 + \cdots + m = \frac{m(m+1)}2.$$

Therefore, for each $k$, the answer is

$$\sum_{\text{active blocks}} \frac{m(m+1)}2.$$

Now we need all $k = 1,2,\dots,n-1$, not just one. Recomputing blocks every time would be $O(n^2)$, which is dead on arrival.

Instead, process thresholds in descending order:

$$k = n-1, n-2, \dots, 1.$$

When moving from $k+1$ to $k$, the only new active edges are positions $i$ where $d_i = k$. No active edge ever disappears. This screams DSU.

Maintain connected components of active edge positions $1,2,\dots,n-1$. Each component is a consecutive block, because edges only connect to immediate neighbors. Also maintain a running value $cur$:

$$cur = \sum_{\text{components}} \frac{size(size+1)}2.$$

When activating a new edge position $x$:

1. It starts as a component of size $1$, increasing $cur$ by $1$.
2. If $x-1$ is active, merge their components.
3. If $x+1$ is active, merge their components.

When merging two components of sizes $a$ and $b$, remove their old contributions and add the merged one:

$$cur \mathrel{-}= \frac{a(a+1)}2,$$ $$cur \mathrel{-}= \frac{b(b+1)}2,$$ $$cur \mathrel{+}= \frac{(a+b)(a+b+1)}2.$$

After activating all edges with $d_i = k$, we have exactly the active edges satisfying $d_i \ge k$, so $ans[k] = cur$.

Why this is correct:

• Every valid subarray of length at least $2$ corresponds to a nonempty interval of adjacent edges.
• That subarray is $k$-exquisite iff every edge in that interval has value at least $k$.
• Active components are maximal consecutive regions where all edges have value at least $k$.
• Each interval inside such a component gives one valid subarray, and no interval can cross an inactive edge.
• The DSU process exactly maintains these active components as $k$ decreases.

Edge cases are clean:

• For $n=2$, there is one edge and only one answer.
• If no edge is active for some $k$, the answer is $0$.
• The maximum answer is $\frac{(n-1)n}{2}$, so use long long.

Complexity per test case is

$$O(n \alpha(n))$$

with DSU, or basically linear unless your inverse Ackermann function starts doing cardio. The total input size is bounded by $2 \cdot 10^5$, so this easily fits.