#include <bits/stdc++.h>

struct heightpair {
    int height;
    int x;
};

void swap(struct heightpair *a, struct heightpair *b) {
    struct heightpair tmp = *a;
    *a = *b;
    *b = tmp;
}

void quicksort(struct heightpair *a, int le, int ri) {
    int i = le, j = ri - 1;
    struct heightpair pivot = a[(rand() %(ri - le)) + le];
    // printf("le = %d, ri = %d, pivot.height = %d\n", le, ri, pivot.height);
    // for (int i = le; i < ri; i++) {
    //     printf("%d\n", a[i]);
    // }
    while (i <= j) {
        while (a[i].height > pivot.height) i++;
        while (a[j].height < pivot.height) j--;
        // printf("i = %d, j = %d\n", i, j);
        if (i <= j) swap(&a[i++], &a[j--]);
    }

    // for (int i = le; i < ri; i++) {
    //     printf("%d\n", a[i]);
    // }
    // printf("----\n");

    if (le < j) quicksort(a, le, j + 1);
    if (i < ri - 1) quicksort(a, i, ri);
}

int maxArea(int *height, int heightSize) {
    struct heightpair *pairs = (struct heightpair *)malloc(heightSize * sizeof(struct heightpair));
    for (int i = 0; i < heightSize; i++) {
        pairs[i].height = height[i];
        pairs[i].x = i;
    }
    quicksort(pairs, 0, heightSize);
    // for (int i = 0; i < heightSize; i++) {
    //     printf("%d, %d\n", pairs[i].height, pairs[i].x);
    // }
    struct heightpair curleft = pairs[0];
    struct heightpair curright = pairs[0];
    int curmax = 0;
    for (int i = 1; i < heightSize; i++) {
        if (pairs[i].x < curleft.x) {
            int vol = (curright.x - pairs[i].x) * pairs[i].height;
            curmax = curmax > vol ? curmax : vol;
            curleft = pairs[i];
        }
        else if (pairs[i].x < curright.x) {
            int vol1 = (pairs[i].x - curleft.x) * pairs[i].height;
            int vol2 = (curright.x - pairs[i].x) * pairs[i].height;
            curmax = curmax > vol1 ? curmax : vol1;
            curmax = curmax > vol2 ? curmax : vol2;
        } else {
            // pairs[i].x > curright.x
            int vol = (pairs[i].x - curleft.x) * pairs[i].height;
            curmax = curmax > vol ? curmax : vol;
            curright = pairs[i];
        }
    }
    return curmax;
}

int main() {
    int nums[] = {1,8,6,2,5,4,8,3,7};
    printf("%d\n", maxArea(nums, sizeof(nums) / sizeof(int)));
    return 0;
}