/**
* Fence(divide & conquer)
*/
//N 1~20000
//Height <= 10000
//#define N 7
//int fence[N] ={7,1,5,9,6,7,3};
//#define N 7
//int fence[N] ={1,4,4,4,4,1,1};
#define N 4
int fence[N] ={1,8,2,2};
//중요한 개념은 가운데를 중심으로 양옆으로 봐 나갈 것이라는 것.
//이 때 가장 큰 직사각형이 지금 중심점에서 시작 하지 않을 수 있으니,
//분할 해서 양옆을 본다.
int solve(int left, int right){
//base case
if(left==right){return fence[left];}
//분할 후
int mid = (right + left) /2;
int l = solve(left,mid);
int r = solve(mid+1,right);
int lo = mid;int hi = mid+1;
//돌아온 것 중 큰 것을 선택한다.
int ret = l > r ? l: r;
//가운데 2개의 사각형을 생각해본다.
int height = fence[lo] < fence[hi] ? fence[lo]:fence[hi];
//이중 가장 큰 직사각형을 만들어야 하므로 더 낮은 판을 기준으로 직사각형을 만든다.
//가운데 직사각형이 양 옆에서 온 것 보다 크다면 ret 사이즈는 이것을 시작점으로,
//그렇지 않다면 양옆의 사이즈를 시작 점으로 삼아서 비교해 나간다.
ret = height *2 > ret ? height *2 : ret;
//그리고 양옆으로 번져나감.
while(lo>left || hi < right){
//아직 오른쪽에 다다르지 않았고, 왼쪽에 다달았거나, 오른쪽으로 가는 것이 왼쪽 보다 클 때.
if(hi < right && (lo == left || fence[lo - 1] < fence[hi+1])){
hi++;
height = height < fence[hi] ? height: fence[hi];
}else{
lo--;
height = height < fence[lo] ? height: fence[lo];
}
ret = ret > height *(hi - lo + 1) ? ret : height *(hi - lo + 1) ;
}
return ret;
}
int main(){
printf("%d
",solve(0,N-1));
}