<p>You may recall that an array <code>arr</code> is a <strong>mountain array</strong> if and only if:</p>

<ul>
	<li><code>arr.length &gt;= 3</code></li>
	<li>There exists some index <code>i</code> (<strong>0-indexed</strong>) with <code>0 &lt; i &lt; arr.length - 1</code> such that:
	<ul>
		<li><code>arr[0] &lt; arr[1] &lt; ... &lt; arr[i - 1] &lt; arr[i]</code></li>
		<li><code>arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]</code></li>
	</ul>
	</li>
</ul>

<p>Given an integer array <code>nums</code>​​​, return <em>the <strong>minimum</strong> number of elements to remove to make </em><code>nums<em>​​​</em></code><em> </em><em>a <strong>mountain array</strong>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The array itself is a mountain array so we do not need to remove any elements.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,1,5,6,2,3,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li>It is guaranteed that you can make a mountain array out of <code>nums</code>.</li>
</ul>

const int INF = 1e9 + 9;

class Solution {
public:

    void update(int pos, int value, vector<int>& tree, int vertex, int left, int right) {
        if (right - left == 1) {
            tree[vertex] = value;
            return;
        }
        int mid = (left + right) / 2;
        if (pos < mid) {
            update(pos, value, tree, vertex * 2 + 1, left, mid);
        } else {
            update(pos, value, tree, vertex * 2 + 2, mid, right);
        }
        tree[vertex] = max(tree[vertex * 2 + 1], tree[vertex * 2 + 2]);
    }

    int get(int queryLeft, int queryRight, vector<int>& tree, int vertex, int left, int right) {
        if (queryLeft >= right || left >= queryRight) {
            return -INF;
        }
        if (queryLeft <= left && right <= queryRight) {
            return tree[vertex];
        }
        int mid = (left + right) / 2;
        return max(
            get(queryLeft, queryRight, tree, vertex * 2 + 1, left, mid),
            get(queryLeft, queryRight, tree, vertex * 2 + 2, mid, right)
        );
    }

    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> compressor = nums;
        compressor.push_back(-INF);
        compressor.push_back(+INF);
        sort(compressor.begin(), compressor.end());
        compressor.erase(unique(compressor.begin(), compressor.end()), compressor.end());
        int k = compressor.size();
        // dpLeft[0] = 0 with num = -INF
        // dpRight[n + 1] = 0 with num = +INF
        vector<int> tree(k << 2, -INF);
        update(0, 0, tree, 0, 0, k);
        vector<int> dpLeft(n + 1);
        dpLeft[0] = 0;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            int index = lower_bound(compressor.begin(), compressor.end(), num) - compressor.begin();
            dpLeft[i] = get(0, index, tree, 0, 0, k) + 1;
            cout << "dpLeft[" << i << "]: " << dpLeft[i] << endl;
            update(index, dpLeft[i], tree, 0, 0, k);
        }
        fill(tree.begin(), tree.end(), -INF);
        update(0, 0, tree, 0, 0, k);
        vector<int> dpRight(n + 1);
        for (int i = n; i >= 1; i--) {
            int num = nums[i - 1];
            int index = lower_bound(compressor.begin(), compressor.end(), num) - compressor.begin();
            dpRight[i] = get(0, index, tree, 0, 0, k) + 1;
            cout << "dpRight[" << i << "]: " << dpRight[i] << endl;
            update(index, dpRight[i], tree, 0, 0, k);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dpLeft[i] >= 2 && dpRight[i] >= 2)
                ans = max(ans, dpLeft[i] + dpRight[i] - 1);
        }
        cout << ans << endl;
        return n - ans;
    }
};
16700