Histogram

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define nn "\n"
#define mod 1000000007

const ll mx = 3e4+7;

ll tree[mx*4];
ll arr[mx];

ll merge(ll left, ll right){
    return min(left,right);
}

void tree_build(ll node, ll ls, ll rs){
    if(ls==rs){
        tree[node] = arr[ls];
        return;
    }
    ll left = node*2;
    ll right = node*2+1;
    ll mid = (ls+rs)/2;

    tree_build(left,ls,mid);
    tree_build(right,mid+1,rs);

    tree[node] = merge(tree[left],tree[right]); // change
}

ll tree_query(ll node, ll ls, ll rs, ll x, ll y){
    if(ls>y || rs<x) return mx; //change
    if(ls>=x && rs<=y) return tree[node];

    ll left = node*2;
    ll right = node*2+1;
    ll mid = (ls+rs)/2;

    ll res1 = tree_query(left,ls, mid, x, y);
    ll res2 = tree_query(right, mid+1, rs, x, y);

    return merge(res1,res2); //change
}

// check ll overflow
void solve(){
    ll n;
    cin>>n;

    for(ll i=1;i<=n;i++) cin>>arr[i];

    tree_build(1,1,n);

    ll result = 0;
    for(ll i=1;i<=n;i++){
        ll x = arr[i];

        ll l = 1, r = i-1, m, lans=0,rans=0;
        while(l<=r){
            m = (l+r)/2;

            if(tree_query(1,1,n,m,i)==x){
                lans = max(lans, i-m);
                r = m-1;
            }
            else l = m+1;
        }
        l = i+1,r = n;
        while(l<=r){
            m = (l+r)/2;

            if(tree_query(1,1,n,i,m)==x){
                rans = max(rans, m-i);
                l = m+1;
            }
            else r = m-1;
        }
        //if(arr[i]==2) cout<<lans<<" "<<rans<<nn;
        result = max(result, 1ll*(lans+1+rans)*arr[i]);
    }
    cout<<result<<nn;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // freopen("reduce.in", "r", stdin);
    // freopen("reduce.out", "w", stdout);
    int tc=1;
    cin>>tc;

    int cases=0;
    while(tc--){
        cout<<"Case "<<++cases<<": ";
        solve();
    }
    return 0;
}