The cost of construction is a power of two.

The cost of construction is $$$2 ^ k$$$, where $$$k$$$ is the highest set bit in $$$n - 1$$$.

Let $$$k$$$ be the highest set bit in $$$n - 1$$$. There will always be a pair of adjacent elements where one of them has the $$$k$$$-th bit set and the other one doesn't, so the cost is at least $$$2^k$$$. A simple construction that reaches it is $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.

Time complexity: $$$O(n)$$$

Bonus: count the number of permutations with the minimum cost.

It is optimal to apply the third operation at most once.

It is optimal to apply the third operation at most once, because is does not decrease $$$a$$$ and always makes $$$b \le a$$$. This means that after we use it, we can only apply the second operation.

If we don't apply the third operation, the answer is $$$b - a$$$.

Suppose we do apply it. Before that, we used the first and second operations some number of times, let the resulting values of $$$a$$$ and $$$b$$$ be $$$a'$$$ and $$$b'$$$ respectively $$$(a \le a', b \le b')$$$. The answer in this case will be $$$(a' - a) + (b' - b) + ((a' \ | \ b') - b') + 1$$$ $$$=$$$ $$$a' + (a' \ | \ b') + (1 - a - b)$$$. This is equivalent to minimizing $$$a' + (a' \ | \ b')$$$, since $$$(1 - a - b)$$$ is constant.

To do that, we can iterate $$$a'$$$ from $$$a$$$ to $$$b$$$. For a fixed $$$a'$$$, we have to minimize $$$a' \ | \ b'$$$, the optimal $$$b'$$$ can be constructed like this:

Set $$$b'$$$ to zero and iterate over bits from highest to lowest. There are 4 cases:

• If current bit of $$$a'$$$ is $$$0$$$ and $$$b$$$ is $$$1$$$, set the current bit of $$$b'$$$ to $$$1$$$.
• If current bit of $$$a'$$$ is $$$0$$$ and $$$b$$$ is $$$0$$$, set the current bit of $$$b'$$$ to $$$0$$$.
• If current bit of $$$a'$$$ is $$$1$$$ and $$$b$$$ is $$$1$$$, set the current bit of $$$b'$$$ to $$$1$$$.
• If current bit of $$$a'$$$ is $$$1$$$ and $$$b$$$ is $$$0$$$, set the current bit of $$$b'$$$ to $$$1$$$ and stop.

This works in $$$O(\log b)$$$ and can also be sped up to $$$O(1)$$$ using bit manipulation.

Time complexity: $$$O(b)$$$ or $$$O(b \log b)$$$

Bonus 1: solve the problem in $$$O(\log b)$$$ or faster.

Bonus 2: prove that is optimal to have either $$$a' = a$$$ or $$$b' = b$$$.

Let's call a segment $$$[l, r]$$$ bad if $$$\gcd(a_l \ldots a_r) = r - l + 1$$$. There at most $$$n$$$ bad segments.

For a fixed $$$l$$$, as $$$r$$$ increases, $$$\gcd(a_l \ldots a_r)$$$ does not increase.

Suppose you change $$$a_i$$$ into a big prime. How does this affect the bad segments?

Read the hints above.

Let's find all of the bad segments. For a fixed $$$l$$$, let's find the largest $$$r$$$ that has $$$\gcd(a_l \ldots a_r) \ge r - l + 1$$$. This can be done with binary search and a sparse table / segment tree. If $$$\gcd(a_l \ldots a_r) = r - l + 1$$$, then the segment $$$[l, r]$$$ is bad.

If we change $$$a_i$$$ into a big prime, no new bad segments will appear. And all bad segments that have $$$i$$$ inside of them will disappear. So we have to find the minimum number of points to cover all of them. This is a standard problem, which can be solved greedily: choose the segment with the smallest $$$r$$$, delete all segments that have $$$r$$$ in them, and repeat. In our case, this is easy to do because our segments are not nested.

Time complexity: $$$O(n \log n \log A)$$$ with a sparse table, where $$$A$$$ is the maximum value of $$$a_i$$$.

Notes:

There are many different modifications to the previous solution, some of them use two pointers (since segments are not nested) and some of them update the answer on the fly while searching for the bad segments. Using a segment tree and two pointers you can get the complexity $$$O(n (\log n + \log A))$$$.

You can also use the fact that for a prefix, there at most $$$O(\log A)$$$ different suffix $$$\gcd$$$ values. This leads to another way to find the bad segments.

It is optimal to add edges of type $$$(1, v)$$$.

Try to check if for a fixed $$$x$$$ the answer is at most $$$ans$$$.

For a fixed $$$x$$$ and answer $$$ans$$$, find the distance between nodes that have $$$depth_v > ans$$$.

For each node, find two children with the deepest subtrees.

Read the hints above.

Let $$$f_{ans}$$$ be the maximum distance between two nodes that have $$$depth_v > ans$$$. If for some $$$x$$$ the answer is at most $$$ans$$$, then either $$$ans \ge depth$$$ or $$$\lceil \frac{f_{ans}}{2} \rceil + x \le ans$$$, since we can add an edge $$$(1, u)$$$ where $$$u$$$ is in the middle of the path connecting the two farthest apart nodes with $$$depth_v > ans$$$. Since $$$f_{ans}$$$ decreases as $$$ans$$$ increases, we can use binary search. Also note that we can use two pointers and increase $$$ans$$$ as we increase $$$x$$$.

How to calculate $$$f_{ans}$$$? Let's find for each node its two children with the deepest subtrees. Let $$$a_v$$$ and $$$b_v$$$ be the depths of their subtrees ($$$a_v \ge b_v$$$). If there are not enough children, set this values to $$$depth_v$$$. If $$$b_v > 0$$$, do $$$f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v)$$$. After this, iterate $$$i$$$ from $$$n - 2$$$ to $$$0$$$ and do $$$f_i = \max(f_i, f_{i + 1})$$$.

Time complexity: $$$O(n)$$$ or $$$O(n \log n)$$$ with binary search.

Note: To solve E1, it is enough to calculate $$$f_{ans}$$$ in $$$O(n)$$$ or $$$O(n \log n)$$$ for each $$$ans$$$. One way to do that is to find the diameter of the resulting tree after repeatedly deleting any leaf that has $$$depth_v \le ans$$$ ($$$1$$$ is also considered a leaf).