Solution
Obviously we will immediately think of the Kruskal algorithm.
Kruskal
Let's consider the edge generated by GCD. We can found that:
For any $i,\ j(i<j)$, when $i\leq{k}\leq{j}$ and $a_k=min(a_i,a_{i+1},...,a_j)$ (so $a_k$ is the minimum value), then $a_k$ can divide all values from $a_i$ to $a_j$.
So start from $k$, we get two farthest points to the left and right. And all points between these two points have edge with length of $a_k$ between them.
So that, when $a_k<p$, we chose this kind of edge as much as possible. After $a_k\geq{p}$, we use edge with length of $p$ directly.
Now the Kruskal part is cleared. The next things is: how to find two farthest points to the left and right.
Disjoint Sets
First of all, if for each $k$, we can start from k and calculate GCD one by one. But it's $O(n^2)$. So we need do some customize on Disjoint sets.
If we think the $O(n^2)$ twice we can found the root cause is: for the points already in the sets, it will be checked again and again.
So it was natural to think: every time, we check from the boundary of the sets. Then we can skip all the points which is already in the sets.
Therefore, not only maintain sets information, we also maintain the left and right boundaries of the collection.
Segment Tree
If every time, we start from the boundary of sets, then we have to do some query for the GCD between $k$ and the boundary. So I use a segment tree to query the interval GCD.
Code
