#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define m_p make_pair #define pi pair<int,int> #define p1 first #define p2 second using namespace std; typedef long long ll; const int maxn=2.5e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,a[maxn],res[maxn],stk[maxn],tp; vector<pi>q1[maxn],q2[maxn]; struct ST { int t[maxn][20],Log_2[maxn]; void init(){ up(i,2,n)Log_2[i]=Log_2[i>>1]+1; up(i,1,n)t[i][0]=a[i]; up(i,1,Log_2[n])up(j,1,n-(1<<i)+1)t[j][i]=max(t[j][i-1],t[j+(1<<i-1)][i-1]); }int qry(int l,int r){ int k=Log_2[r-l+1]; return max(t[l][k],t[r-(1<<k)+1][k]); } }T; struct SegTree { struct node { ll lz,mn; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define lz(p) d[p].lz #define mn(p) d[p].mn void pu(int p){mn(p)=min(mn(ls(p)),mn(rs(p)));} void cl(int p,ll x){mn(p)+=x,lz(p)+=x;} void pd(int p){cl(ls(p),lz(p)),cl(rs(p),lz(p)),lz(p)=0;} void bd(int l,int r,int p){lz(p)=0; if(l==r){ mn(p)=a[l];return; }int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } void upd(int l,int r,int s,int t,int p,int x){ if(l>r)return; if(l<=s&&t<=r){cl(p,x);return;}pd(p); int mid=s+t>>1; if(l<=mid)upd(l,r,s,mid,ls(p),x);if(r>=mid+1)upd(l,r,mid+1,t,rs(p),x);pu(p); }int qry(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return mn(p);pd(p); int mid=s+t>>1,mn=1e9; if(l<=mid)mn=min(mn,qry(l,r,s,mid,ls(p)));if(r>=mid+1)mn=min(mn,qry(l,r,mid+1,t,rs(p))); return mn; } }T2; void sol(){tp=0,stk[0]=0,T2.bd(1,n,1),T.init(); up(i,1,n){if(i>1)T2.upd(i-1,i-1,1,n,1,a[i]); while(tp&&a[stk[tp]]<=a[i]){ T2.upd(max(stk[tp-1],1),stk[tp]-1,1,n,1,a[i]-a[stk[tp]]); tp--; }for(auto it:q1[i])res[it.p2]=min(res[it.p2],T2.qry(it.p1,i-1,1,n,1)+T.qry(it.p1,i)); stk[++tp]=i; } } void slv(){ n=read(),q=read(); up(i,1,n)a[i]=read();T.init(); up(i,1,n)q1[i].clear(),q2[i].clear(); up(i,1,q){res[i]=1e9; int l=read(),r=read(); res[i]=a[l]+a[r]+T.qry(l,r); q1[r].p_b(m_p(l,i)); q2[l].p_b(m_p(r,i)); }sol(); reverse(a+1,a+n+1); up(i,1,n)q1[i].clear(); up(i,1,n)for(auto it:q2[i])q1[n-i+1].p_b(m_p(n-it.p1+1,it.p2)); sol();up(i,1,q)printf("%d\n",res[i]); }int main(){ //freopen("divide.in","r",stdin),freopen("divide.out","w",stdout); int t=read();while(t--)slv(); return 0; }