The smallest possible sum is $$$1 + 2 + \ldots + k$$$.

In an optimal answer, for all $$$1 \le i \le n$$$, $$$\operatorname{lcm}(i, p_i) = i \cdot p_i$$$.

$$$\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$$$.

The operation only decreases numbers.

An array is sorted if there is no index $$$i$$$ such that $$$a_i > a_{i + 1}$$$.

Suppose there is an index $$$i$$$ such that $$$a_i > a_{i + 1}$$$. What operations do you need to perform to make $$$a_i \le a_{i + 1}$$$?

$$$\operatorname{d}(u; v) \le 2 \cdot min(a_1 \ldots a_n)$$$

diameter $$$\le 2 \cdot min(a_1 \ldots a_n)$$$

diameter $$$\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$

Binary search on the answer or a clever greedy.

[tutorial:1712E]