#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
 
struct T {
    int mn, mx, diff;
    // conquer
    T operator+(T const &rhs) const {
        int _mn = min(mn, rhs.mn);
        int _mx = max(mx, rhs.mx);
        int _diff = max({diff, rhs.diff, rhs.mx-mn});
        return {_mn, _mx, _diff};
    }
};
 
// max diff is assumed 0 if a is mono decreasing
T max_diff(int a[], int st, int ed) {
    if (st >= ed) return {INT_MAX, INT_MIN, 0};
    if (st + 1 == ed) return {a[st], a[st], 0};
    // divide
    int md = st + (ed - st) / 2;
    return max_diff(a, st, md) + max_diff(a, md, ed);
}
 
int main() {
    int a[] = {12, 9, 18, 3, 7, 11, 6, 15, 6, 1, 10};
    cout << max_diff(a, 0, sizeof(a)/sizeof(int)).diff << endl;
    return 0;
}
 

I2luY2x1ZGUgPGNsaW1pdHM+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBUIHsKICAgIGludCBtbiwgbXgsIGRpZmY7CiAgICAvLyBjb25xdWVyCiAgICBUIG9wZXJhdG9yKyhUIGNvbnN0ICZyaHMpIGNvbnN0IHsKICAgICAgICBpbnQgX21uID0gbWluKG1uLCByaHMubW4pOwogICAgICAgIGludCBfbXggPSBtYXgobXgsIHJocy5teCk7CiAgICAgICAgaW50IF9kaWZmID0gbWF4KHtkaWZmLCByaHMuZGlmZiwgcmhzLm14LW1ufSk7CiAgICAgICAgcmV0dXJuIHtfbW4sIF9teCwgX2RpZmZ9OwogICAgfQp9OwoKLy8gbWF4IGRpZmYgaXMgYXNzdW1lZCAwIGlmIGEgaXMgbW9ubyBkZWNyZWFzaW5nClQgbWF4X2RpZmYoaW50IGFbXSwgaW50IHN0LCBpbnQgZWQpIHsKICAgIGlmIChzdCA+PSBlZCkgcmV0dXJuIHtJTlRfTUFYLCBJTlRfTUlOLCAwfTsKICAgIGlmIChzdCArIDEgPT0gZWQpIHJldHVybiB7YVtzdF0sIGFbc3RdLCAwfTsKICAgIC8vIGRpdmlkZQogICAgaW50IG1kID0gc3QgKyAoZWQgLSBzdCkgLyAyOwogICAgcmV0dXJuIG1heF9kaWZmKGEsIHN0LCBtZCkgKyBtYXhfZGlmZihhLCBtZCwgZWQpOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBhW10gPSB7MTIsIDksIDE4LCAzLCA3LCAxMSwgNiwgMTUsIDYsIDEsIDEwfTsKICAgIGNvdXQgPDwgbWF4X2RpZmYoYSwgMCwgc2l6ZW9mKGEpL3NpemVvZihpbnQpKS5kaWZmIDw8IGVuZGw7CiAgICByZXR1cm4gMDsKfQo=