int largestRectangleArea(int* heights, int heightsSize){
    int left[100000], right[100000], stack[100000];
    int top = -1, max = 0;
    for (int i = 0; i < heightsSize; i++) {
        while (top >= 0 && heights[i] < heights[stack[top]]) {
            right[stack[top]] = i;
            if  (top > 0) {
                left[stack[top]] = stack[top-1];
            }
            else {
                left[stack[top]] = -1;
            }
            top--;
        }
        top++;
        stack[top] = i;
    }
    while (top >= 0) {
        right[stack[top]] = heightsSize;
        if (top > 0) {
            left[stack[top]] = stack[top-1];
        }
        else {
            left[stack[top]] = -1;
        }
        top--;
    }

    for (int j = 0; j < heightsSize; j++) {
        max = fmax(max, heights[j] * (right[j] - left[j] - 1));       
    }

    return max;
}