Solution 1: By Segment tree with O(nlogn) time complexity.

#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define ff                  first
#define ss                  second
#define sz(x)               x.size()
#define qu                  queue
#define pqu                 priority_queue
#define vc                  vector
#define vi                  vector<int>
#define vll                 vector<long long>
#define pii                 pair<int,int>
#define pis                 pair<int,string>
#define psi                 pair<string,int>
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)          for(int i=0;i<n;i++)
#define for1(i,n)          for(int i=1;i<=n;i++)
#define forcmp(i,n)        for(int i=1;i<n;i++)
#define forrev(i,n)        for(int i=n-1; i>=0; i--)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define forba(i,b,a)       for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000000
#define inf                 100000000
#define mx                  100005

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

int input[mx],n;
pii tree[3*mx];

void build(int node,int low,int high)
{
    if(low==high) {tree[node]=make_pair(input[low],low); return; }
    int left=2*node;
    int right=2*node+1;
    int mid=(low+high)/2;
    build(left,low,mid);
    build(right,mid+1,high);
    tree[node]=min(tree[left],tree[right]);
}

pii query(int node,int low,int high,int qlow,int qhigh)
{
    if(low>qhigh || high<qlow) return pii(inf,inf);
    else if(low>=qlow && high<=qhigh) return tree[node];
    int left=2*node;
    int right=2*node+1;
    int mid=(low+high)/2;
    pii l=query(left,low,mid,qlow,qhigh);
    pii r=query(right,mid+1,high,qlow,qhigh);
    return min(l,r);
}

ll area(int i,int j)
{
    if(j<i) return 0;
    pii mini=query(1,1,n,i,j);
    ll a1=(j-i+1)*mini.ff;
    ll a2=max(area(i,mini.ss-1),area(mini.ss+1,j));
    return max(a1,a2);
}

int main()
{
    int t;
    sf(t);
    for1(z,t)
    {
        sf(n);
        for1(i,n) sf(input[i]);
        build(1,1,n);
        case2(z);
        pf("%lld\n",area(1,n));
    }
    return 0;
}

Solution 2: By stack with O(n) time complexity

Note:
This is the same problem as in SPOJ – HISTOGRA – Largest Rectangle in a Histogram. But here the most important point to be noted that in SPOJ, the Time Limit is 0.409 sec where in Light OJ , the same problem has Time limit of 2 sec…. So here in Light OJ, the problem can be solved by Segment tree ( the way in which I had done above in Solution 1) with O(nlogn) time complexity. But there in SPOJ, the Segment tree solution will get TLE since the O(nlogn) complexity will cross the Time limit of 0.409 sec. So here, I have approached in stack solution which is of O(n)  time complexity.

Here is the solution link by stack.