Thakur needs at most 5 turns to finish all the monsters optimally. It can be proved.
Lets say in a turn thakur choses to fight with \(i\)th monster, for an optimal condition the maximum monster he can avoid fighting after \(i\) is 4 which means fight with the \(i+5\)th monster after \(i\). If he choses the \(i+6\)th monster after \(i\) it is not optimal because he can chose a monster in the middle (\(i+3\)th) monster. So in every turn he can kill around 1/5 monster at least and in 5 turns he can kill all the monsters in the worst case.

now lets dive into the dp solution. (discussed in 1 based indexing)
lets say
\(dp[i][j]\) = the minimum amount of health lost in the prefix of \(j\) if the \(j\)th monster is killed in the \(i\)th turn.

so the final answer will be \(MIN(dp[i][n])\) \([i=1,2,3,4,5]\)

if any monster in \(j\)th position is killed in \(i\)th turn then it will harm thakur for previous \((i-1)\) turn decreasing his health by \(Aj * (i-1)\)

so the transition will be \(dp[i][j] = Aj * (i-1) + MIN(dp[k][j-1]\) \((k=1,2,3,4,5\) and \(k!=i)\)

But there is a problem in this transition. We can not be sure if the \(dp[k][j-1]\) state contains any value which was taken from \(dp[k][j-2] (where k==i)\). It means thakur killed \(j-2\), and \(j\) th monster in the same turn which does not satisfy the condition of avoiding fight with two consecutive monster after fighting a monster.

To avoid this we can save two value (min and 2nd min) in each state \(dp[i][j]\) with their respective \(i\) (from which turn of the previous state the current state was taken).

By this we can avoid taking any value from \(dp[k][j-1]\) which contains any value which was taken from \(dp[k][j-2]\) where \(i==k\).

the base case will be \(dp[i][1] = Aj * (i-1)\) \([i=1,2,3,4,5]\)

time complexity : O(N55*5)

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    ll n; cin>>n;
    ll a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    ll m = 5;
    vector<vector<vector<ll>>> dp(m,vector<vector<ll>>(n+1,vector<ll>(4,1e17)));
    
    // first column
    for(ll i=0;i<m;i++) dp[i][0][0] = a[0]*i;
    
    // second column 
    dp[0][1][0] = dp[1][0][0]; dp[0][1][1] = 1; dp[0][1][2] = dp[2][0][0]; dp[0][1][3] = 2; // first row
    dp[1][1][0] = 0 + a[1]; dp[1][1][1] = 0; dp[1][1][2] = a[1]+dp[2][0][0];  dp[1][1][3] = 2; // second row
    for(ll i=2;i<m;i++)
    {
        dp[i][1][0] = a[1]*i;
        dp[i][1][1] = 0;
        dp[i][1][2] = a[1]*i + a[0];
        dp[i][1][3] = 1;
    }
    //dp
    for(ll col=2;col<n;col++)
    {
        for(ll i=0;i<m;i++)
        {
            // dp[i][col][0] and dp[i][col][1];
            for(ll j=0;j<m;j++)
            {
                if(i==j) continue;
                if(dp[j][col-1][0] < dp[i][col][0] && dp[j][col-1][1] != i)
                {
                    dp[i][col][0] = dp[j][col-1][0];
                    dp[i][col][1] = j;
                }
                if(dp[j][col-1][2] < dp[i][col][0] && dp[j][col-1][3] != i)
                {
                    dp[i][col][0] = dp[j][col-1][2];
                    dp[i][col][1] = j;
                }
            }

            ll k = dp[i][col][1];
            // dp[i][col][2] and dp[i][col][3];
            for(ll j=0;j<m;j++)
            {
                if(j==i || j==k) continue;
                if(dp[j][col-1][0] < dp[i][col][2] && dp[j][col-1][1] != i)
                {
                    dp[i][col][2] = dp[j][col-1][0];
                    dp[i][col][3] = j;
                }
                if(dp[j][col-1][2] < dp[i][col][2] && dp[j][col-1][3] != i)
                {
                    dp[i][col][2] = dp[j][col-1][2];
                    dp[i][col][3] = j;
                }
            }

            dp[i][col][0] += a[col]*i;
            dp[i][col][2] += a[col]*i;
        }
    }

    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<" "<<dp[i][j][2]<<" "<<dp[i][j][3]<<" | ";
        }
        cout << endl;
    }

    ll ans = 1e18;
    for(int i=0;i<m;i++)
    {
        ans = min({ans , dp[i][n-1][0], dp[i][n-1][2]});
    }
    cout<<ans<<endl;
}
int main()
{
    int t; cin>>t; while(t--) solve();
}