#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

void FENCE();
int Area(int left, int right, vector<int> vtr);
int maximum(int a, int b);
int minimum(int a, int b);

int main() {
    int nTestCase;

    cin >> nTestCase;

    while (nTestCase--) {
        //int start = clock();
        FENCE();
        //int end = clock();
        //double time = (double)(end - start);
        //cout << "Access Time : " << time / CLOCKS_PER_SEC << endl;
    }
    return 0;
} // main()

void FENCE() {
    int nFence;
    int nHeight;
    vector<int> vtrInput;

    cin >> nFence;

    //srand((unsigned)time(NULL));

    while (nFence--) {
        //테스트케이스 입력
        cin >> nHeight;
        //테스트케이스 생성
        //nHeight = rand()%10000;
        //cout << nHeight << " ";
        vtrInput.push_back(nHeight);
    }
    //cout << endl <<  "MAXIMUM AREA : ";
    cout << Area(0, vtrInput.size() - 1, vtrInput) << endl;
    vtrInput.clear();
} // FENCE()

int Area(int nLeft, int nRight, vector<int> nVtrHeight) {
    // 좌극 == 우극일때 높이를 반환
    if (nLeft == nRight) return nVtrHeight[nLeft];
    // 중간 경계면을 기준으로 분할
    int nMid = (nLeft + nRight) / 2;
    int nMaxOne = maximum(Area(nLeft, nMid, nVtrHeight), Area(nMid + 1, nRight, nVtrHeight));
    // 중간 경계면을 포함하는 넓이를 계산
    int nLow = nMid;
    int nHigh = nMid + 1;
    int nHeight = minimum(nVtrHeight[nLow], nVtrHeight[nHigh]);
    // 좌우값 중 큰값과 경계면을 포함하는 두펜스의 넓이 중 큰 값을 저장
    nMaxOne = maximum(nMaxOne, nHeight * 2);
    // 경계면을 좌극값과 우극값 사이에서 확장
    while (nLeft < nLow || nHigh < nRight) {
        // 우측으로 확장할 공간이 있고 &&
        // ( 좌측으로 확장할 공간이 없거나 || 우측으로 확장하는 경우에 더 큰 높이값을 가져가는 경우 )
        if (nHigh < nRight && (nLow == nLeft || nVtrHeight[nLow - 1] < nVtrHeight[nHigh + 1])) {
            // 우측으로 확장
            ++nHigh;
            // 확장한면에서 가장 낮은 높이값을 저장
            nHeight = minimum(nHeight, nVtrHeight[nHigh]);
        }
        // 좌측으로 확장할 공간이 있고 &&
        // ( 우측으로 확장할 공간이 없거나 || 좌측으로 확장하는 경우에 더 큰 높이값을 가져가는 경우 )
        else {
            // 좌측으로 확장
            --nLow;
            nHeight = minimum(nHeight, nVtrHeight[nLow]);
        }
        // (좌우값 중 큰값과 경계면을 포함하는 두 펜스의 넓이중 큰값) 과 경계면을 포함하는 면의 넓이중에 큰값을 저장
        nMaxOne = maximum(nMaxOne, nHeight*(nHigh - nLow + 1));
    }
    return nMaxOne;
} // maximumArea()

// 큰값을 반환
int maximum(int a, int b) {
    if (a > b) return a;
    else return b;
} // max()

// 낮은값을 반환
int minimum(int a, int b) {
    if (a < b) return a;
    else return b;
} // min()

책에 있는 알고리즘을 이용해서 풀었는데 TLE가 뜨네요
시간계산해보니 입력값이 20000개 일때 평균 6~9초정도 걸리는데 어느부분을 수정해야할까요?