/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int i;
    vector<int> V;
    TreeNode *make(int start,int end)
    {
        if(start>end) return NULL;
        int mid= start + (end-start)/2;
        TreeNode *t=(TreeNode *)malloc(sizeof(TreeNode));
        t->left=make(start,mid-1);
        t->val=V[i++];
        t->right=make(mid+1,end);
        return t;
    }
    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        i=0;
        V=num;
        int n=num.size();
        return make(0,n-1);
    }
};

LyoqCiAqIERlZmluaXRpb24gZm9yIGJpbmFyeSB0cmVlCiAqIHN0cnVjdCBUcmVlTm9kZSB7CiAqICAgICBpbnQgdmFsOwogKiAgICAgVHJlZU5vZGUgKmxlZnQ7CiAqICAgICBUcmVlTm9kZSAqcmlnaHQ7CiAqICAgICBUcmVlTm9kZShpbnQgeCkgOiB2YWwoeCksIGxlZnQoTlVMTCksIHJpZ2h0KE5VTEwpIHt9CiAqIH07CiAqLwpjbGFzcyBTb2x1dGlvbiB7CnB1YmxpYzoKICAgIGludCBpOwogICAgdmVjdG9yPGludD4gVjsKICAgIFRyZWVOb2RlICptYWtlKGludCBzdGFydCxpbnQgZW5kKQogICAgewogICAgICAgIGlmKHN0YXJ0PmVuZCkgcmV0dXJuIE5VTEw7CiAgICAgICAgaW50IG1pZD0gc3RhcnQgKyAoZW5kLXN0YXJ0KS8yOwogICAgICAgIFRyZWVOb2RlICp0PShUcmVlTm9kZSAqKW1hbGxvYyhzaXplb2YoVHJlZU5vZGUpKTsKICAgICAgICB0LT5sZWZ0PW1ha2Uoc3RhcnQsbWlkLTEpOwogICAgICAgIHQtPnZhbD1WW2krK107CiAgICAgICAgdC0+cmlnaHQ9bWFrZShtaWQrMSxlbmQpOwogICAgICAgIHJldHVybiB0OwogICAgfQogICAgVHJlZU5vZGUgKnNvcnRlZEFycmF5VG9CU1QodmVjdG9yPGludD4gJm51bSkgewogICAgICAgIC8vIFN0YXJ0IHR5cGluZyB5b3VyIEMvQysrIHNvbHV0aW9uIGJlbG93CiAgICAgICAgLy8gRE8gTk9UIHdyaXRlIGludCBtYWluKCkgZnVuY3Rpb24KICAgICAgICBpPTA7CiAgICAgICAgVj1udW07CiAgICAgICAgaW50IG49bnVtLnNpemUoKTsKICAgICAgICByZXR1cm4gbWFrZSgwLG4tMSk7CiAgICB9Cn07