<p>There are <code>n</code> soldiers standing in a line. Each soldier is assigned a <strong>unique</strong> <code>rating</code> value.</p>

<p>You have to form a team of 3 soldiers amongst them under the following rules:</p>

<ul>
	<li>Choose 3 soldiers with index (<code>i</code>, <code>j</code>, <code>k</code>) with rating (<code>rating[i]</code>, <code>rating[j]</code>, <code>rating[k]</code>).</li>
	<li>A team is valid if: (<code>rating[i] &lt; rating[j] &lt; rating[k]</code>) or (<code>rating[i] &gt; rating[j] &gt; rating[k]</code>) where (<code>0 &lt;= i &lt; j &lt; k &lt; n</code>).</li>
</ul>

<p>Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).</p>

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

<pre>
<strong>Input:</strong> rating = [2,5,3,4,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 
</pre>

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

<pre>
<strong>Input:</strong> rating = [2,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> We can&#39;t form any team given the conditions.
</pre>

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

<pre>
<strong>Input:</strong> rating = [1,2,3,4]
<strong>Output:</strong> 4
</pre>

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

<ul>
	<li><code>n == rating.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= rating[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the integers in <code>rating</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    struct treap {
        int p;
        int v;
        int size;
        treap *left, *right;
        treap(int v_) {
            p = random();
            v = v_;
            size = 1;
            left = right = nullptr;
        }
        ~treap() {
            delete left;
            delete right;
        }
    };
    void update_size(treap *root) {
        if (root == nullptr)
            return;
        int l = get_size(root->right); 
        int r = get_size(root->left);
        root->size = l + r + 1; 
    }
    treap* merge(treap* a, treap* b) {
        if (a == nullptr)
            return b;
        if (b == nullptr)
            return a;
        if (a->p > b->p) {
            a->right = merge(a->right, b);
            update_size(a);
            return a;
        }else {
            b->left = merge(a, b->left);
            update_size(b);
            return b;
        }
    }
    pair<treap*, treap*> split(treap* root, int k) {
        if (root == nullptr)
            return {nullptr, nullptr};
        if (root->v < k) {
            auto [a, b] = split(root->right, k);
            root->right = a;
            update_size(root);
            return {root, b};
        }else {
            auto [a, b] = split(root->left, k);
            root->left = b;
            update_size(root);
            return {a, root};
        }
    }
    treap* insert(treap* root, int v) {
        auto [a, b] = split(root, v);
        return merge(merge(a, new treap(v)), b);
    }
    inline int get_size(treap* root) {
        return (root == nullptr)? 0:root->size;
    }
    int less_count(treap* root, int v) {
        if (root == nullptr)
            return 0;
        if (root->v < v) {
            return get_size(root->left) + 1 + less_count(root->right, v);
        }else {
            return less_count(root->left, v);
        }
    }
    int greater_count(treap* root, int v) {
        if (root == nullptr)
            return 0;
        if (root->v > v) {
            return get_size(root->right) + 1 + greater_count(root->left, v);
        }else {
            return greater_count(root->right, v);
        }
    }
    int numTeams(vector<int>& rating) {
        vector<int> smaller(rating.size(), 0);
        vector<int> bigger(rating.size(), 0);
        
        treap *a = nullptr, *b = nullptr;
        for(int i = 0; i < rating.size(); i++) {
            smaller[i] = less_count(a, rating[i]);
            bigger[i] = greater_count(a, rating[i]);
            a = insert(a, rating[i]);
        }
        int res = 0;
        for(int i = rating.size()-1; i >= 0; i--) {
            res += smaller[i] * greater_count(b, rating[i]);
            res += bigger[i] * less_count(b, rating[i]);
            b = insert(b, rating[i]);
        }
        delete a;
        delete b;
        return res;
    }
};
20099