F. Довідки 25/25

#include <bits/stdc++.h>

#define int long long
#define pb push_back
#define mp make_pair
//#define ull long long

typedef unsigned long long ull;

using namespace std;

const int DEBUG = 0;
const int INF = ((int)1e15 + 10);
const int N = 100010;
const int md = (int)1e7 + 19;


int n,k;
int l[N],r[N];
int ans = 0;

vector<int> d(N);
vector<vector<int> > g(N);

void dfs(int v,int cur = 0,int counter = 1)
{
    if(counter == k)
    {
        ans = max(ans,cur);
        return;
    }
    if(abs(l[v]-v) > abs(r[v] - v))
        dfs(l[v],cur + abs(l[v]-v),counter+1);
    else
        dfs(r[v],cur + abs(r[v]-v),counter+1);

    return;
}

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

    cin >> n >> k;

    vector<int> a(n);

    for(int i = 0; i < n; i++)
        cin >> a[i];

    vector<int> pos(k+1,-1);
    vector<int> start;

    for(int i = 0; i < n; i++)
    {
        if(a[i] == 1)
            start.pb(i);
        if(pos[a[i]] == -1)
            pos[a[i]] = i;
        if(pos[a[i]+1] == -1)
            l[i] = i;
        else
            l[i] = pos[a[i]+1];
    }

    pos.assign(k+1,-1);

    for(int i = n - 1; i >= 0; i--)
    {
        if(pos[a[i]] == -1)
            pos[a[i]] = i;
        if(pos[a[i]+1] == -1)
            r[i] = i;
        else
            r[i] = pos[a[i]+1];
    }

    for(auto x : start)
        dfs(x);

    if(n <= 5000)
    {
        for(int i = 0; i < n; i++)
            g[a[i]].pb(i);
        queue<int> q;
        for(auto x : start)
            q.push(x);
        int v;
        while(!q.empty())
        {
            v = q.front();
            q.pop();
            for(auto x : g[a[v]+1])
            {
                if(d[x] < d[v] + abs(v-x))
                {
                    d[x] = d[v] + abs(v-x);
                    q.push(x);
                }
            }
        }
        for(auto x : g[k])
            ans = max(ans,d[x]);
    }

    cout << ans;

    return 0;
}