#include<bits/stdc++.h> using namespace std; long long _,n,a[100005],dp[100005][11],dp2[100005][11]; int main(){ scanf("%lld",&_); while(_--){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); for(int j=0;j<=10;j++){ dp[i][j]=dp2[i][j]=0x3f3f3f3f3f3f3f3f; } } for(int j=0;j<=10;j++){ dp[0][j]=dp2[n+1][j]=0; } for(int i=1;i<=n;i++){ for(int j=0;j<=10;j++){ if(a[i]<=j){ dp[i][j]=dp[i-1][j]; } else{ dp[i][j]=min(dp[i][j],dp[i-1][a[i]]+(a[i]-j)*i); } // printf("%lld ",dp[i][j]); } // printf("\n"); } dp2[n+1][0]=0; for(int i=n;i>=1;i--){ for(int j=0;j<=10;j++){ if(a[i]<=j){ dp2[i][j]=dp2[i+1][j]; } else{ dp2[i][j]=min(dp2[i][j],dp2[i+1][a[i]]+(a[i]-j)*(n-i+1)); } } } long long ans=0x3f3f3f3f3f3f3f3f; for(int i=1;i<=n;i++){ long long sum=0x3f3f3f3f3f3f3f3f; for(int j=0;j<=a[i];j++){ sum=min(sum,dp[i-1][j]+dp2[i+1][a[i]-j]+j*i+(a[i]-j)*(n-i+1)); } ans=min(ans,sum); // printf("%lld ",ans); } printf("%lld\n",ans); } }