加强版见 U568378。

我现在写完了 std，原本计划卡掉树状数组优化 dp 做法，但成功失败。

在这题弱化版卡掉是可行的，因为 $O(n)$ 做法常数较小，但是加强版需要进行双指针，由于 vector 过慢我换用了链表（但这样访址就必然不连续了/ll）而且常数较大，和树状数组做法拉平。

所以是干脆不卡了还是用一些阴间手段干掉树状数组（

std 如下。

#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
#define mp make_pair
#define pb push_back
#define dbg puts("-------------qaqaqaqaqaqaqaqaqaq------------")
#define pl (p<<1)
#define pr ((p<<1)|1)
#define pii pair<int,int>
#define inf 30000000
#define mod 998244353
#define eps 1e-9
#define ent putchar('\n')
#define sp putchar(' ')
using namespace std;
inline int read(){
	char c=getchar(),f=0;int t=0;
	for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
	for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
	return f?-t:t;
}
inline void write(int x){
	static int t[25];int tp=0;
	if(x==0) return(void)(putchar('0'));else if(x<0) putchar('-'),x=-x;
	while(x) t[tp++]=x%10,x/=10;
	while(tp--) putchar(t[tp]+48);
}
mt19937 gen(time(NULL));
inline int randint(int l,int r){
    return gen()%(r-l+1)+l;
}
const int N=1e7+10;
int n,cnt,ans;
int a[N],pre[N],suf[N];
int nxt[N],las[N],lasp[N],st[N],en[N];
int qaq[N],pq[N],sq[N];
inline int mymin(int x,int y){return x<y?x:y;}
inline int myabs(int x){return x<0?-x:x;}
signed main(){
	int last=0;
	for(int id=9;id<=9;id++){
		cerr<<"Case:"<<id<<" start."<<endl;
		char awa[30];
	    // sprintf(awa,"bdHD%d.in",id);
	    // freopen(awa,"r",stdin);
		// sprintf(awa,"bdHD%d.out",id);
		// freopen(awa,"w",stdout);
		int T=read();
		while(T--){
			n=read();
			pre[1]=suf[n]=ans=inf,cnt=0;
			for(int i=1;i<=n;i++){
				a[i]=read();
				qaq[++cnt]=i;
				if(lasp[a[i]]==0) st[a[i]]=cnt;
				else nxt[lasp[a[i]]]=cnt,las[cnt]=lasp[a[i]];
				en[a[i]]=cnt;
				lasp[a[i]]=cnt;
			}
			for(int i=1;i<=n;i++){
				for(int j=st[i];j!=0;j=nxt[j]){
					if(qaq[j]>=3) pq[j]=myabs(a[qaq[j]-1]-a[1]);
					else pq[j]=inf;
				}
				for(int j=nxt[st[i]];j!=0;j=nxt[j]) pq[j]=mymin(pq[las[j]],pq[j]);
				for(int j=st[i];j!=0;j=nxt[j]){
					if(qaq[j]<=n-2) sq[j]=myabs(a[qaq[j]+1]-a[n]);
					else sq[j]=inf;
				}
				for(int j=las[en[i]];j!=0;j=las[j]) sq[j]=mymin(sq[nxt[j]],sq[j]);
			}
			ans=myabs(a[1]-a[n])+n;
			for(int i=2;i<=n;i++) pre[i]=mymin(pre[i-1],myabs(a[i]-a[1]));
			for(int i=n-1;i>=1;i--) suf[i]=mymin(suf[i+1],myabs(a[i]-a[n]));
			for(int i=2;i<=n-2;i++) ans=mymin(ans,n+myabs(a[1]-a[i])+myabs(a[n]-a[i+1]));
			for(int i=3;i<=n-2;i++) ans=mymin(ans,n+2+pre[i-1]+suf[i+1]);
			for(int i=1;i<n;i++){
				for(int l=st[i],r=st[i+1];l!=0;l=nxt[l]){
					if(qaq[l]>=3){
						for(;r!=0&&qaq[r]<=qaq[l];) r=nxt[r];
						if(r!=0){
							ans=mymin(pq[l]+sq[r]+1+n,ans);
						}
					}
				}
				for(int l=st[i+1],r=st[i];l!=0;l=nxt[l]){
					if(qaq[l]>=3){
						for(;r!=0&&qaq[r]<=qaq[l];) r=nxt[r];
						if(r!=0){
							ans=mymin(pq[l]+sq[r]+1+n,ans);
						}
					}
				}
				for(int l=st[i];nxt[l]!=0;l=nxt[l]){
					if(qaq[l]>=3){
						ans=mymin(pq[l]+sq[nxt[l]]+n,ans);
					}
				}
			}
			for(int i=0;i<=n;i++) qaq[i]=sq[i]=pq[i]=lasp[i]=las[i]=nxt[i]=st[i]=en[i]=0;
			write(ans),ent;
		}
		cerr<<"Case:"<<id<<" done. Spend:"<<clock()*1./CLOCKS_PER_SEC-last<<"."<<endl;
		last=clock()*1./CLOCKS_PER_SEC;
	}
	return 0;
}