Назовём массив неоднозначным, если существует стро...

Мы можем решить задачу, сведя её к следующему наблюдению.

Предположим, что массив $b[1 \ldots n]$ после изменений имеет по крайней мере два способа разбить себя на два непустых подмассива, каждый из которых является перестановкой. Легко заметить, что если рассмотреть разбиения по индексу $i$ (то есть $b[1\ldots i]$ и $b[i+1\ldots n]$) условие того, что обе части – перестановки, означает:

• Для префикса длины $i$ должно выполняться: $$b[1\ldots i] \text{ содержит ровно числа } 1,2,\dots,i.$$
• Для суффикса длины $n-i$ должно выполняться: $$b[i+1\ldots n] \text{ содержит ровно числа } 1,2,\dots,(n-i).$$

Оказывается, что если в массиве существует более одного способа такого разбиения, то они обязательно имеют вид «слева маленький кусок» и «справа маленький кусок»: то есть существуют $k$ с $1\le k<\frac{n}{2}$ такие, что

• $b[1\ldots k]$ – перестановка чисел от $1$ до $k$,
• $b[k+1\ldots n-k]$ – перестановка чисел от $k+1$ до $n-k$,
• $b[n-k+1\ldots n]$ – перестановка чисел от $1$ до $k$.

Действительно, если рассмотреть два разбиения (например, по индексам $k$ и $n-k$, где $k<n-k$), то условие, что оба разбиения корректны, приводит к тому, что на пересечениях вынуждены появляться именно эти наборы чисел.

Пусть мы хотим получить такое решение с минимальным числом операций (замен элементов). Заметим, что мы можем независимо «подправлять» три участка:

1. Префикс $1\ldots k$ должен стать перестановкой чисел $1,\dots,k$. Если на данном участке уже присутствуют некоторые числа из множества $\{1,\dots,k\}$ (каждое можно использовать только один раз), то мы можем «сохранить» их – другими словами, экономим операцию. Максимальное число позиций, которые можно не трогать, равно количеству различных чисел из $\{1,\dots,k\}$, появившихся в $a[1\ldots k]$ (каждое считается не более одного раза).

2. Аналогично, суффикс $n-k+1\ldots n$ должен стать перестановкой чисел $1,\dots,k$. Его можно «сохранить» в количестве – число различных $x\in\{1,\dots,k\}$, которые встречаются хотя бы один раз в $a[n-k+1\ldots n]$.

3. Средний участок $k+1\ldots n-k$ должен стать перестановкой чисел $\{k+1,\,k+2,\dots,n-k\}$. Здесь можно сохранить те $x$ из этого множества, которые встречаются хотя бы раз на участке. При этом можно показать, что для данного $x$ условие появления в участке $a[k+1\ldots n-k]$ равносильно тому, что для этого $x$ выполняется неравенство

$$k\le \min\Bigl(x-1,\; n-x,\; n-\mathrm{occ}(x),\; \mathrm{last}(x)-1\Bigr),$$

где $\mathrm{occ}(x)$ – первый индекс появления $x$ в массиве $a$, а $\mathrm{last}(x)$ – последний.

Таким образом, если для каждого участка знать «сбережения» (то есть число позиций, где не надо менять элемент), то стоимость корректировки участка – длина участка минус число сбережённых позиций.

Заметим ещё – поскольку разбиение должно быть неоднозначным – достаточно найти такое $k$ с $1\le k<\frac{n}{2}$ для которого суммарная стоимость (префикс + средний участок + суффикс) минимальна.

Чтобы вычислить «сбережения» эффективно, можно сделать следующее:

(A) Префикс.
Для $x\in\{1,\dots,k\}$ «сохраняем», если $x$ встречается в $a[1\ldots k]$. Это равносильно тому, что первый индекс появления $x$ (обозначим $\mathrm{occ}(x)$) не больше $k$. Тогда общее число сбережённых позиций – это число таких $x$ (при этом каждый $x$ можно посчитать ровно один раз).
Чтобы быстро вычислять для всех $k$ сумму по $x=1\ldots k$ индикатора $\mathbf{1}_{\{\mathrm{occ}(x)\le k\}}$ – удобно воспользоваться разностным массивом: для каждого $x$ добавляем единицу начиная с $k_0=\max(x,\mathrm{occ}(x))$.

(B) Суффикс.
Аналогично – для $x\in\{1,\dots,k\}$ сохраняем, если $x$ встречается в $a[n-k+1\ldots n]$. Это равносильно тому, что $\mathrm{last}(x)\ge n-k+1$. Опять можно использовать разностный массив: для каждого $x$ прибавляем единицу начиная с $k_0=\max(x,\; n-\mathrm{last}(x)+1)$.

(C) Средний участок.
Здесь разрешённые числа – $\{k+1,\dots,n-k\}$ (их ровно $n-2k$). Для каждого числа $x$ (при условии, что $x$ появляется в $a$) можно доказать, что $x$ будет встречаться в $a[k+1\ldots n-k]$ для всех $k$ от $1$ до

$$T_x=\min\Bigl(x-1,\; n-x,\; n-\mathrm{occ}(x),\; \mathrm{last}(x)-1\Bigr).$$

Тогда если для каждого $x$ посчитать $T_x$ и с помощью разностного массива (или суммирования по группам) построить массив, где для каждого $k$ узнаём число $x$ с $T_x\ge k$, то получим число сбережённых позиций на среднем участке.

Обозначим:

• $cost_{pref}(k)= k-$ (число сбережённых в префиксе),
• $cost_{suff}(k)= k-$ (число сбережённых в суффиксе),
• $cost_{mid}(k)= (n-2k)-$ (число сбережённых на среднем участке).

Тогда суммарная стоимость для данного $k$ равна:

$$cost(k)=cost_{pref}(k)+cost_{mid}(k)+cost_{suff}(k).$$

Ответ — минимум $cost(k)$ по $k=1,\dots,\lfloor\frac{n-1}{2}\rfloor$.

Ниже приведён полный код на C++ (с комментариями), который решает задачу. (Обратите внимание – код поддерживает оба формата входных данных, когда $f=1$ – стандартный список, и $f=2$ – генерация по рекуррентной формуле.)

---

cpp
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, f;
    if(!(cin >> n >> f))
        return 1;
    // Массив a будем считать с индексами от 1 до n.
    vector<int> a(n+1, 0);
    if(f == 1){
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
    } else { // f == 2
        int m;
        long long X, Y, Z;
        cin >> m >> X >> Y >> Z;
        for (int i = 1; i <= m; i++){
            cin >> a[i];
        }
        // Для i от m+1 до n: a[i] = 1 + (X * a[i-2] + Y * a[i-1] + Z) mod n.
        for (int i = m+1; i <= n; i++){
            long long val = (X * a[i-2] + Y * a[i-1] + Z) % n;
            a[i] = (int)(val + 1);
        }
    }
 
    // 1. Для каждого числа x (от 1 до n) находим:
    //    occ[x]  = первый индекс, где a[i]==x (если не встретилось, = n+1)
    //    last[x] = последний индекс, где a[i]==x (если не встретилось, = 0)
    vector<int> occ(n+1, n+1), last(n+1, 0);
    for (int i = 1; i <= n; i++){
        int val = a[i];
        if(val < 1 || val > n) continue;
        occ[val] = min(occ[val], i);
        last[val] = i;
    }
 
    // 2. Для префикса: x (от 1 до n) можно "сохранить" на префиксе длины k,
    //    если k >= max(x, occ[x]). Используем разностный массив.
    vector<int> diffPrefix(n+2, 0);
    for (int x = 1; x <= n; x++){
        if(occ[x] <= n){
            int start = max(x, occ[x]);
            if(start <= n)
                diffPrefix[start]++;
        }
    }
    vector<int> prefixSave(n+1, 0);
    for (int k = 1; k <= n; k++){
        prefixSave[k] = diffPrefix[k] + (k > 1 ? prefixSave[k-1] : 0);
    }
    // Тогда cost_pref(k) = k - prefixSave[k].
 
    // 3. Аналогично для суффикса (индексы n-k+1..n, допустимые числа 1..k):
    //    x сохраняется, если k >= max(x, n - last[x] + 1).
    vector<int> diffSuffix(n+2, 0);
    for (int x = 1; x <= n; x++){
        if(last[x] > 0){
            int start = max(x, n - last[x] + 1);
            if(start <= n)
                diffSuffix[start]++;
        }
    }
    vector<int> suffixSave(n+1, 0);
    for (int k = 1; k <= n; k++){
        suffixSave[k] = diffSuffix[k] + (k > 1 ? suffixSave[k-1] : 0);
    }
    // Тогда cost_suff(k) = k - suffixSave[k].
 
    // 4. Для среднего участка [k+1, n-k] (размер n-2k, допустимые числа k+1..n-k).
    //    Для числа x, которое встречается, пусть L = occ[x] и R = last[x].
    //    x появится на среднем участке, если существует i \in [k+1, n-k] с a[i]==x.
    //    Это равносильно условиям: x \in [k+1, n-k], R >= k+1 и L <= n-k.
    //    Тогда x будет присутствовать для всех k таких, что:
    //         k <= min(x-1, n-x, n - occ[x], last[x]-1).
    //    Обозначим T_x = min(x-1, n-x, n - occ[x], last[x]-1).
    //    Тогда x "сохраняется" на среднем участке для всех k от 1 до T_x.
    //    С помощью разностного метода (или аккумулирования) можно посчитать для каждого k число x с T_x >= k.
    vector<int> countT(n+1, 0);
    for (int x = 1; x <= n; x++){
        if(last[x] == 0) continue;
        int t1 = x - 1;
        int t2 = n - x;
        int t3 = n - occ[x]; 
        int t4 = last[x] - 1;
        int T = min({t1, t2, t3, t4});
        if(T < 1) continue;
        if(T > n) T = n;
        countT[T]++;
    }
    // Построим суффиксную сумму: для каждого k будем знать число x таких, что T_x >= k.
    vector<int> suffixCount(n+2, 0);
    suffixCount[n] = countT[n];
    for (int t = n-1; t >= 1; t--){
        suffixCount[t] = countT[t] + suffixCount[t+1];
    }
    // Для среднего участка: cost_mid(k) = (n - 2*k) - (число сбережённых),
    // где число сбережённых = suffixCount[k].
 
    // 5. Перебираем все возможные k, где k от 1 до floor((n-1)/2) (т.к. 2*k < n)
    int maxK = (n - 1) / 2;
    int ans = INT_MAX;
    for (int k = 1; k <= maxK; k++){
        int costPrefix = k - prefixSave[k];
        int costSuffix = k - suffixSave[k];
        int segLength = n - 2 * k;
        int saveMiddle = suffixCount[k]; // число x с T_x >= k
        int costMiddle = segLength - saveMiddle;
        int total = costPrefix + costMiddle + costSuffix;
        ans = min(ans, total);
    }
 
    cout << ans << "\n";
    return 0;
}

---

Краткое пояснение

1. Ввод и генерация массива.
   Если $f=1$ – читаем массив $a[1\ldots n]$ напрямую, иначе (при $f=2$) по заданной схеме генерируем оставшиеся элементы.

2. Предварительная обработка.
   Для каждого $x$ вычисляем $occ[x]$ (первое появление) и $last[x]$ (последнее). Это нужно для оценки «сбережённых» позиций на каждом из трёх участков.

3. Подсчёт сбережений.
   Для префикса и суффикса с помощью разностных массивов определяем, сколько разрешённых чисел (каждое считать один раз) уже встречается. Для среднего участка для каждого $x$ считаем $T_x=\min\{x-1,\, n-x,\, n-\mathrm{occ}(x),\, \mathrm{last}(x)-1\}$ – для всех $k\le T_x$ число $x$ можно «сохранить».

4. Перебор $k$.
   Для каждого допустимого $k$ (с $2k<n$) вычисляем суммарную стоимость исправлений и выбираем минимум.

---

Этот код решает задачу за $O(n)$ (с дополнительными O(n) при генерации и суммировании) и подходит для ограничений задачи.

Вы можете скопировать и скомпилировать данный код на C++ (стандарт C++11 и выше).