#include<bits/stdc++.h> #define int long long #define doub long double #define PII pair<int,int> #define fir first #define sec second #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) #define lb(x) ((x)&(-(x))) #define PC(x) __builtin_popcountll(x) #define ctz(x) __builtin_ctzll(x) #define clz(x) __builtin_clzll(x) #define Flush() fflush(stdout) #define insert emplace // #define push_back emplace_back #define endl '\n' using namespace std; const int N=2.5e5+7; int n,q,a[N]; int LG[N],ST[N][19]; inline void GetLG(){ LG[0]=-1; for(int i=1;i<N;i++)LG[i]=LG[i>>1]+1; } inline int cmp(int i,int j){ return a[i]>=a[j]?i:j; } inline void GetST(){ for(int i=1;i<=n;i++)ST[i][0]=i; for(int j=1;j<=LG[n];j++){ for(int i=1;i<=n-(1<<j)+1;i++){ ST[i][j]=cmp(ST[i][j-1],ST[i+(1<<j-1)][j-1]); } } } inline int QryPos(int l,int r){ int t=LG[r-l+1]; return cmp(ST[l][t],ST[r-(1<<t)+1][t]); } struct SGT{ int Tg[N<<2],Min[N<<2]; inline void pu(int p){ Min[p]=min(Min[lc(p)],Min[rc(p)]); }inline void Calc(int p,int t){ Tg[p]+=t,Min[p]+=t; }inline void pd(int p){ Calc(lc(p),Tg[p]);Calc(rc(p),Tg[p]); Tg[p]=0; }inline void Build(int p,int l,int r){ Tg[p]=0,Min[p]=0; if(l==r)return; int mid=l+r>>1; Build(lc(p),l,mid);Build(rc(p),mid+1,r); }inline void Add(int p,int l,int r,int L,int R,int dt){ if(l>r||L>R)return; if(L<=l&&r<=R)return void(Calc(p,dt)); int mid=l+r>>1;pd(p); if(L<=mid)Add(lc(p),l,mid,L,R,dt); if(R>mid)Add(rc(p),mid+1,r,L,R,dt); pu(p); }inline int Qry(int p,int l,int r,int L,int R){ if(l>r||L>R)return 3e9; if(L<=l&&r<=R)return Min[p]; int mid=l+r>>1;pd(p);int ret=3e9; if(L<=mid)ret=min(ret,Qry(lc(p),l,mid,L,R)); if(R>mid)ret=min(ret,Qry(rc(p),mid+1,r,L,R)); return ret; } }T; int h[N]; struct QR{ int l,r,id; }; vector<QR> QRL[N],QRR[N]; int qa[N]; int st[N],Tp; inline void slv(){ cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)QRL[i].clear(),QRR[i].clear(); a[0]=a[n+1]=1e9+1; GetST(); for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; qa[i]=a[l]+a[r]+a[QryPos(l+1,r-1)]; h[i]=QryPos(l,r); QRR[r].push_back((QR){h[i]+1,r-1,i}); QRL[l].push_back((QR){l+1,h[i]-1,i}); } T.Build(1,1,n); for(int i=1;i<=Tp;i++)st[i]=0; Tp=0; st[++Tp]=0; for(int i=1;i<=n;i++){ T.Add(1,1,n,i,i,a[i]); if(i>1)T.Add(1,1,n,i-1,i-1,a[i]); while(Tp&&a[st[Tp]]<a[i]){ T.Add(1,1,n,max(st[Tp-1],1ll),st[Tp]-1,a[i]-a[st[Tp]]); Tp--; } st[++Tp]=i; for(auto qr:QRR[i]){ qa[qr.id]=min(qa[qr.id],a[h[qr.id]]+T.Qry(1,1,n,qr.l,qr.r)); } } T.Build(1,1,n); for(int i=1;i<=Tp;i++)st[i]=0; Tp=0; st[++Tp]=n+1; for(int i=n;i>=1;i--){ T.Add(1,1,n,i,i,a[i]); if(i<n)T.Add(1,1,n,i+1,i+1,a[i]); while(Tp&&a[i]>a[st[Tp]]){ T.Add(1,1,n,st[Tp]+1,min(st[Tp-1],n),a[i]-a[st[Tp]]); Tp--; } st[++Tp]=i; for(auto qr:QRL[i]){ qa[qr.id]=min(qa[qr.id],a[h[qr.id]]+T.Qry(1,1,n,qr.l,qr.r)); } } for(int i=1;i<=q;i++)cout<<qa[i]<<endl; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); GetLG(); #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); freopen("1.out","w",stdout); #endif int T;cin>>T; while(T--)slv(); cout.flush();return 0; }