Given two equally sized arrays A and B of size N. A is empty and B has some values.
You need to fill A with an element X such that X belongs to B.
The only operations allowed are:
1. Copy B[i] to A[i].
2. Cyclic shift B by 1 to the the right.
You need to minimise the number of operations.
The first line contains a single positive integer N(1 ≤ N ≤ 106), denoting the size of the arrays.
Next line contains N space separated positive integers denoting the elements of the array B(1 ≤ B[i ≤ 105)].
Output a single integer, denoting the minimum number of operations required.
In the first test case:
We can have 5 steps as: fill first element, shift, fill second element, shift, fill third element.
Initially, A = [_, _, _, B = [1, 2, 3]]
After step 1, A = [1, _, _, B = [1, 2, 3]]
After step 2, A = [1, _, _, B = [3, 1, 2]]
After step 3, A = [1, 1, _, B = [3, 1, 2]]
After step 4, A = [1, 1, _, B = [2, 3, 1]]
After step 5, A = [1, 1, 1, B = [2, 3, 1]]
## Input
The first line contains a single positive integer N(1 ≤ N ≤ 106), denoting the size of the arrays.Next line contains N space separated positive integers denoting the elements of the array B(1 ≤ B[i ≤ 105)].
## Output
Output a single integer, denoting the minimum number of operations required.
[samples]
## Note
In the first test case:We can have 5 steps as: fill first element, shift, fill second element, shift, fill third element.Initially, A = [_, _, _, B = [1, 2, 3]]After step 1, A = [1, _, _, B = [1, 2, 3]]After step 2, A = [1, _, _, B = [3, 1, 2]]After step 3, A = [1, 1, _, B = [3, 1, 2]]After step 4, A = [1, 1, _, B = [2, 3, 1]]After step 5, A = [1, 1, 1, B = [2, 3, 1]]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the size of arrays $ A $ and $ B $.
Let $ B = (b_0, b_1, \dots, b_{N-1}) $ be the initial array of integers.
Array $ A $ is initially empty: $ A = (\bot, \bot, \dots, \bot) $.
A **copy operation** at index $ i $ sets $ A[i] = B[i] $.
A **right cyclic shift** transforms $ B $ into $ (b_{N-1}, b_0, b_1, \dots, b_{N-2}) $.
**Constraints**
1. $ 1 \leq N \leq 10^6 $
2. $ 1 \leq b_i \leq 10^5 $ for all $ i \in \{0, 1, \dots, N-1\} $
**Objective**
Minimize the total number of operations (copy + shift) required to make $ A[i] = x $ for all $ i $, for some $ x \in B $.
For each candidate value $ x \in B $, let $ S_x = \{ i \in \{0, \dots, N-1\} \mid b_i = x \} $ be the set of indices where $ x $ appears in $ B $.
For each $ i \in S_x $, the number of right shifts needed to align $ b_i $ to position $ j $ is $ (j - i) \mod N $.
To fill $ A[j] = x $, we must perform $ k $ shifts and one copy at the moment $ x $ is at position $ j $.
The minimal operations to fill all positions with $ x $ is:
$$
\min_{\text{order of filling}} \left( \text{number of shifts} + |S_x| \right)
$$
where the shifts are minimized by optimally ordering the copy operations.
For fixed $ x $, the minimal total operations is:
$$
|S_x| + \min_{\sigma \in \text{Perms}(S_x)} \sum_{k=1}^{|S_x|} \left( \sigma(k) - \sigma(k-1) \right) \mod N
$$
where $ \sigma(0) = 0 $, and $ \sigma $ is the order of indices in $ S_x $ to copy.
Equivalently, the minimal shifts needed to cover all positions in $ S_x $ in cyclic order is:
$$
N - \max_{i,j \in S_x} \left( (j - i) \mod N \right)
$$
But more directly: the minimal number of shifts is $ N - d_{\max} $, where $ d_{\max} $ is the maximum gap between consecutive occurrences of $ x $ in the circular array.
Thus, for each $ x \in B $, define:
- Let $ \text{positions}_x = \{ i_0, i_1, \dots, i_{m-1} \} $, sorted, $ m = |S_x| $.
- Compute gaps: $ g_k = (i_{k} - i_{k-1}) \mod N $ for $ k = 1, \dots, m $, with $ i_{-1} = i_{m-1} - N $.
- Let $ g_{\max} = \max_k g_k $.
- Then operations for $ x $: $ N - g_{\max} + m $.
**Final Objective**
$$
\min_{x \in B} \left( N - g_{\max}^{(x)} + |S_x| \right)
$$