We equivalently view the cyclically shifting as a pointer starting at $j$ that moves left and right cyclically.

Let's use 0-indexing that wraps around modulo $N$ (so $A_i=A_{i\pmod N}$).

Linear Time Solution 1:

Claim. For a given starting index $j$, the optimal pointer route consists of at most one turn (LR or RL).

Proof. The indices visited from $j$ form a contiguous segment including $j$. Whatever this interval is, it can be traversed by going all the way to one end, turning, and going to the other end. This is optimal because the indices $j$, $l$, and $r$ must all be visited at some point, either in the order $j \rightarrow l \rightarrow r$ or $j \rightarrow r \rightarrow l$. This requires at least $\min(|j-l|+|r-l|, |j-r|+|l-r|)$ movements. (done proof)

Without loss of generality, say the optimal route from $j$ starts with L. Then the path must look like $L...L R ...R$. Or, equivalently, visiting an interval $[l, r]$ by going to $l\le j$ first then right to $r$. This costs $(j-l)+(r-l) = j+(r-2l)$. It suffices to consider right-minimal $[l, r]$ -- $r$ must the smallest integer $\ge l$ such that $[l, r]$ covers all of $S$. We can sweep $j$ from $0$ to $N-1$ and

• maintain the smallest $r$ for $l=j$, and
• track the minimal $(r-2l)$ for all right-minimal intervals $[l, r]$ such that $l\le j$.

Incrementing $j$ incurs an $O(1)$ time to do the first and amortized linear time to do the second.

We account for the start moving right case analogously.

Claire's Python Code:

n = int(input())
a = list(map(int, input().split()))
a = [x-1 for x in a]

A = a + a
ans = [2*n] * (2*n)

def solve(arr, _ans):
    m = len(arr)
    need = len(set(a))
    cnt = [0] * n
    r = -1
    best = 10**18

    for j in range(m):
        while r + 1 < m and need > 0:
            r += 1
            cnt[arr[r]] += 1
            if cnt[arr[r]] == 1:
                need -= 1

        if need == 0:
            best = min(best, r - 2*j) 

        _ans[j] = min(_ans[j], j + best)

        cnt[arr[j]] -= 1
        if cnt[arr[j]] == 0:
            need += 1

for _ in range(2):
    solve(A, ans)
    A.reverse()
    ans.reverse()

for i in range(n):
   print(min(ans[i], ans[n + i]), end=' ')

Linear Time Solution 2:

We note that the optimal route can always be split into two parts:

• (second) Walking across a minimal interval $[l,r]$ either from left to right or from right to left. Here, an interval $[l,r]$ is minimal if it contains all distinct integers in $A$ but neither $[l+1,r]$ nor $[l,r-1]$ do.
• (first) Choosing a minimal interval and walking to one of its endpoints.

Initialize $ans_i=\infty$ for all $i$ from $0$ to $N-1$. We can handle the two parts as follows:

• The set of minimal intervals is contained within the set of right-minimal intervals, so for each right-minimal interval $[l,r]$ we set $ans_l=\min(ans_l, r-l)$ and $ans_r=\min(ans_r, r-l)$.
• Then we relax the answers (while there exist adjacent $i$ and $j$ such that $ans_i>ans_j+1$, set $ans_i=ans_j+1$). We can do this efficiently by first setting $ans_{i+1}=\min(ans_{i+1}, ans_i+1)$ for $i$ from $0$ to $2N-1$, then the same thing in the reverse direction.

Note: We compute right-minimal intervals $[l,r]$ in a different way from Solution 1. Specifically, we first

• Compute for each index $i$ the smallest integer $nxt_i>i$ such that $A_{nxt_i}=A_i$, as well as the value of $r$ when $l=0$.
• Then we update $r$ for each $l$ in increasing order. Specifically, when you transition from $l$ to $l+1$, you must set $r=\max(r, nxt_l)$.

Ben's C++ code:

#include <bits/stdc++.h>
using namespace std;

template <class T> using V = vector<T>;
#define all(x) begin(x), end(x)

void ckmin(int &a, int b) { a = min(a, b); }
void ckmax(int &a, int b) { a = max(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    V<int> A(N);
    for (int &t : A) cin >> t;

    V<int> lst(N + 1, -1), nxt(N, -1);
    V<int> ans(N, N);
    auto add_ival = [&](int l, int r) {
        assert(l <= r);
        int len = r - l;
        ckmin(ans.at(l), len);
        ckmin(ans.at(r % N), len);
    };
    int r = 0;
    for (int i = 0; i < 2 * N; ++i) {
        int &ls = lst.at(A.at(i % N));
        if (ls == -1) {
            ckmax(r, i);
        } else if (ls < N) nxt.at(ls) = i;
        ls = i;
    }
    for (int i = 0; i < N; ++i) {
        add_ival(i, r);
        assert(nxt.at(i) != -1);
        ckmax(r, nxt.at(i));
    }
    for (int it = 0; it < 2; ++it) {
        for (int i = 0; i < N; ++i) ckmin(ans.at((i + 1) % N), ans.at(i) + 1);
        for (int i = N - 1; i >= 0; --i)
            ckmin(ans.at(i), ans.at((i + 1) % N) + 1);
    }
    for (int i = 0; i < N; ++i) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
}