#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+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 void GetST(){ for(int i=1;i<=n;i++)ST[i][0]=a[i]; for(int j=1;j<=LG[n];j++){ for(int i=1;i<=n-(1<<j)+1;i++){ ST[i][j]=max(ST[i][j-1],ST[i+(1<<j-1)][j-1]); } } } inline int Max(int l,int r){ int t=LG[r-l+1]; return max(ST[l][t],ST[r-(1<<t)+1][t]); } inline void slv(){ cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i]; GetST(); while(q--){ int l,r;cin>>l>>r; int Ans=3e9; Ans=min(Ans,a[l]+Max(l+1,r-1)+a[r]); for(int i=l+1;i<=r-1;i++)Ans=min(Ans,Max(l,i-1)+a[i]+Max(i+1,r)); cout<<Ans<<endl; } } signed main(){ GetLG(); #ifndef ONLINE_JUDGE freopen("divide.in","r",stdin); freopen("divide.out","w",stdout); #endif int T;cin>>T; while(T--)slv(); }