inline int mymin(int a, int b){ return a<b?a:b;}
inline int mymax(int a, int b){ return a>b?a:b;}
int fence[20000];
int cache[20000][20000];
int solve(int left, int right){
if(left==right){return fence[left];}
int mid = (left + right)/2;
int &ret = cache[left][right];
if(ret != 0){return ret;}
ret = mymax(solve(left,mid),solve(mid+1,right));
int l = mid;
int r = mid+1;
int height = mymin(fence[l],fence[r]);
ret = mymax(height*2,ret);
//ㅣ 이 아직 left보다 크거나 r 이 right 보다 작은 동안 계속 돈다.
//height 는 가운데 두 개 판자중 낮은 것의 높이부터 시작.
while(left < l || r < right){
// r 이 right 보다 작고, l이 이미 left에이미 도달 해서 더 갈 수 없거나 오른쪽 fence 가 더 높을때 오른쪽 으로 간다.
if(r < right && (l==left || fence[l-1] < fence[r+1])){
r++;
height = mymin(fence[r],height);
}else{
l++;
height = mymin(fence[l],height);
}
//ret와 지금 가진 좌우 * 높이 중 더 큰것을 취한다.
ret = mymax(ret, height * ( r - l +1 ));
}
return ret;
}