解题思路

显然，如果将$a_i$变为序列以外的数，相比于变为序列中的数而言，代价一定是较大的。所以说一定是将$a_i$变为序列内的其他数。

显然，对于每一个$a_i$，只有第一次出现的$a_i$会对数组$c$产生影响。如果将第一次出现的$a_i$改为其他值，那么对于数值为$a_i$的数，只有在下一次$a_i$的出现会对数组$c$产生影响。所以我们只需要存储$a_i$的第一次出现和第二次出现的位置即可。

接下来，我们开始继续考虑$a_i$对代价所产生的影响。显然，对于第一次出现的$a_i$，它对代价的贡献为$i+(i+1)+(i+2)+…+n$，在这里将它记为S(i)。

最后只剩下对于$a_i$的变化所引起的代价改变的讨论了。我们假设将$a_i$变为$a_j$，(假设$a_j$也是第一次出现)，且$a_i$的下一次出现为$a_k$，针对$i$与$j$的大小进行分类讨论。

第一种情况 j<i

略微推导可以得知，更改所造成变化的贡献为$|a_i-a_j|+S(k)-S(i)$,$S(k)$与$S(i)$都是确定的值，因此只要找到与$a_i$最接近的$a_j$即可。

第二种情况 j>i

同上推导可知，更改造成的变化的贡献为
$$|a_i-a_j|-S(i)+S(k)-S(j)+S(i)=|a_i-a_j|+S(k)-S(j)$$

在讨论的过程中，为了方便，我们对于$a_i，a_j$的大小进行进一步讨论（将绝对值去掉）。

a[j]>a[i]

$$=S(k)-a_i+a_j-S(j)$$

接下来对于变量我们可以用一个树状数组来维护$a_j-S(j)$的最大值或$S(j)-a_j$的最小值即可。

a[j]<a[i]

同上

至此讨论完成

代码

#pragma GCC optimize(1)
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include <iostream>//抄
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include <vector>

using namespace std;
const int N=5e5+10;

int n,a[N];
map<int,int> m;
set<int> s;
vector<int> V[N];
int v[N];
long long ans=0;
struct bit{
    long long c[N];
    bit(){
        memset(c,0xcf,sizeof c);
    }
    int lowbit(int x){
        return x&(-x);
    }
    void add(int k,long long x){
        for(;k<=N;k+=lowbit(k)){
            c[k]=max(c[k],x);
        }
    }
    long long query(int x){
        long long ans=0xcfcfcfcfcfcfcfcf;
        for(;x;x-=lowbit(x)){
            ans=max(ans,c[x]);
        }
        return ans;
    }
}T1,T2;
long long sum(int l,int r){
    if(l>r) return 0;
    return (long long)(l+r)*(r-l+1)/2;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int id=0;
    for(int i=1;i<=n;i++){
        if(!m.count(a[i])) m[a[i]]=++id;
        ans+=(long long )i*id;
        if(V[m[a[i]]].size()<2) V[m[a[i]]].push_back(i),v[i]=V[m[a[i]]].size();
    }
    vector<int> TMP(n);
    for(int i=0;i<n;i++) TMP[i]=a[i+1];
    sort(TMP.begin(),TMP.end());
    auto ed=unique(TMP.begin(),TMP.end());
    for(int i=1;i<=id;i++){
        if(V[i].size()<2) V[i].push_back(n+1);
    }
    long long res=ans;
    s.insert(a[1]);
    for(int i=2;i<=n;i++){
        if(v[i]==1){
            int ID=m[a[i]];
            auto it=s.lower_bound(a[i]);
            int cost=2e9;
            if(it!=s.end()) cost=min(cost,*it-a[i]);
            if(it!=s.begin()) it--,cost=min(cost,a[i]-*it);
            ans=min(ans,res-sum(V[ID][0],V[ID][1]-1)+cost);
            s.insert(a[i]);
        }
    }
    if(v[n]==1){
        ans=min(ans,res-n);
        int idx=lower_bound(TMP.begin(),ed,a[n])-TMP.begin()+1;
        T1.add(id-idx+1,n-a[n]);
        T2.add(idx,n+a[n]);
    }
    for(int i=n-1;i>=1;i--){
        if(v[i]==1){
            int ID=m[a[i]];
            int p=V[ID][1];
            int idx=lower_bound(TMP.begin(),ed,a[i])-TMP.begin()+1;
            long long res1=res-(T1.query(id-idx)-sum(p,n)+a[i]);
            long long res2=res-(T2.query(idx-1)-sum(p,n)-a[i]);
            ans=min(ans,res1);
            ans=min(ans,res2);
            T1.add(id-idx+1,sum(i,n)-a[i]);
            T2.add(idx,sum(i,n)+a[i]);
        }
    }
    printf("%lld\n",ans);
}