class NumArray {
private:
    vector<int> tree;
    int size;
public:
    NumArray(vector<int> nums) {
        size = nums.size();
        if (size == 0) return;
        tree.resize(size * 10);
        buildTree(nums, 0, 0, size - 1);
    }
    
    void buildTree(vector<int>& nums, int treeIndex, int left, int right) {
        if (left == right) {    
            tree[treeIndex] = nums[left];
            return;
        };
        int mid = (right - left) / 2 + left;
        buildTree(nums, treeIndex * 2 + 1, left, mid);
        buildTree(nums, treeIndex * 2 + 2, mid + 1, right);
        tree[treeIndex] = tree[treeIndex * 2 + 1] + tree[treeIndex * 2 + 2];
        
        return;
    }
    
    void update(int i, int val) {
        updateST(i, val, 0, size - 1, 0);
    }
    
    void updateST(int index, int val, int left, int right, int treeIndex) {
        if (left == right) {tree[treeIndex] = val; return;}
        
        int mid = left + (right - left) / 2;
        if (index > mid) 
            updateST(index, val, mid + 1, right, treeIndex * 2 + 2);
        else 
            updateST(index, val, left, mid, treeIndex * 2 + 1);
        
        tree[treeIndex] = tree[treeIndex * 2 + 1] + tree[treeIndex * 2 + 2];
        
        return;
    }
    
    int sumRange(int i, int j) {
        int ret = sumRangeST(i, j, 0, 0, size - 1);
        // cout << ret << endl;
        return ret;
    }
    
    int sumRangeST(int targetLeft, int targetRight, int treeIndex, int currentLeft, int currentRight) {
        if (targetLeft == currentLeft 
                && targetRight == currentRight) 
            return tree[treeIndex];
        
        int mid = currentLeft + (currentRight - currentLeft) / 2;
        
        int left = 0;
        int right = 0;
        
        if (targetLeft <= mid) 
            left = sumRangeST(targetLeft, min(targetRight, mid), 
                              treeIndex * 2 + 1, currentLeft, mid);min(mid, targetRight);
        if (targetRight >= mid + 1) 
            right = sumRangeST(max(mid + 1, targetLeft), targetRight, treeIndex * 2 + 2, mid + 1, currentRight);
        

        return left + right;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* ret = reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
    
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        
        ListNode* slow = head;
        ListNode* quick = head;
        while(quick && quick->next && quick->next->next) {
            slow = slow->next;
            quick = quick->next->next;
        }
        ListNode* newHead = reverse(slow->next);
        slow->next = NULL;
        
        //Merge crossly from head and newHead;
        ListNode* cur = head;
        ListNode* another = newHead;
        while (cur && another) {
            ListNode* temp = cur;
            cur = cur->next;
            temp->next = another;
            temp = another;
            another = another->next;
            temp->next = cur;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* ret = reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == NULL || head->next == NULL || m == n) return head;
        ListNode* fake = new ListNode(-1);
        fake->next = head;
        ListNode* start = fake;
        while (m > 1) {
            start = start->next;
            --m; --n;
        }
        ListNode* end = start;
        while (n > 0) {
            --n;
            end = end->next;
        }
        ListNode* temp = end;
        end = end->next;
        temp->next = NULL;
        ListNode* h = reverse(start->next);
        start->next->next = end;
        start->next = h;
        
        return fake->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

class LRUCache {
private:
    unordered_map<int, int> timer;
    unordered_map<int, int> cache;
    int maxSize;
    int time;
public:
    LRUCache(int capacity) {
        maxSize = capacity;
        time = 0;
    }
    
    int get(int key) {
        auto iter = cache.find(key);
        if (iter == cache.end() ) return -1;
        
        time += 1;
        timer[key] = time;
        return iter->second;
    }
    void evict() {
        int early = INT_MAX;
        int target = -1;
        for (auto iter = timer.begin(); iter != timer.end(); iter++) {
            if (iter->second < early) {
                early = iter->second;
                target = iter->first;
            }
        }
        cache.erase(target);
        timer.erase(target);
    }
    
    void put(int key, int value) {
        cache[key] = value;
        time += 1;
        timer[key] = time;
        if (cache.size() > maxSize) evict();
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

class LRUCache {

private:
    unordered_map<int, list<pair<int, int>>::iterator> map;
    list<pair<int, int>> lis;
    int size;
public:
    LRUCache(int capacity) {
        size = capacity;
    }
    
    int get(int key) {
        auto iter = map.find(key);
        if (iter == map.end()) return -1;
        
        auto index = iter->second;
        lis.push_front(*index);
        lis.erase(index);
        map[key] = lis.begin();
        
        return index->second;
    }
    
    void put(int key, int value) {
        
        if (map.find(key) != map.end() )
            lis.erase(map[key]);
        lis.push_front(make_pair(key, value));
        map[key] = lis.begin();
        if (lis.size() > size) {
            int deleteKey = lis.back().first;
            lis.pop_back();
            map.erase(deleteKey);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (sum % k) return false;
        int target = sum / k;
        vector<bool> visited(nums.size(), false);
        return helper(target, nums, visited, k, 0, 0);
    }
    
    bool helper(int target, vector<int>& nums, vector<bool>& visited, int k, int currentSum, int start) {
        if (k == 0) return true;
        if (target == currentSum) return helper(target, nums, visited, k - 1, 0, 0);
        for (int i = start; i < nums.size(); i++) {
            if (visited[i] == true) continue;
            visited[i] = true;
            if ( helper(target, nums, visited, k, currentSum + nums[i], i + 1) ) return true;
            visited[i] = false;
        }
        return false;
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int size = nums.size();
        if (size == 0 || size == 1) return false;
        int sum = 0;
        for (int i = 0; i < size; i++) sum += nums[i];
        
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        vector<vector<bool>> dp(size + 1, vector<bool>(target+1, false));
        for (int i = 0; i <= size; i++) dp[i][0] = true;
            
        for (int i = 1; i <= size; i++) {
            for(int amount = nums[i - 1]; amount <= target; ++amount)
                if(dp[i - 1][amount - nums[i - 1]]) {
                    dp[i][amount] = true;
                    dp[i][amount - nums[i - 1]] = true;
                }
            if (dp[i][target]) return true;
        }
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        sort(head, NULL);
        return head;
    }
    
    void sort(ListNode* start, ListNode* end) {
        if (start == end || start->next == end) return;
        ListNode* mid = partition(start, end);
        sort(start, mid);
        sort(mid->next, end);
    }
    
    ListNode* partition(ListNode* start, ListNode* end) {
        int midValue = start->val;
        ListNode* cur = start->next;
        ListNode* mid = start;
        while (cur != end) {
            if (cur->val < midValue) {
                mid = mid->next;
                swap(mid->val, cur->val);
            }
            cur = cur->next;
        }
        swap(mid->val, start->val);
        return mid;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* ret = sort(head);
        return ret;
    }
    
    ListNode* sort(ListNode* start) {
        if (!start || !start->next) return start;
        ListNode* slow = start;
        ListNode* quick = start;
        while (quick && quick->next && quick->next->next) {
            slow = slow->next;
            quick = quick->next->next;
        }
        ListNode* left = sort(slow->next);
        slow->next = NULL;
        ListNode* right = sort(start);
        return merge(left, right);
    }
    
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* fake = new ListNode(-1);
        ListNode* cur = fake;
        while (left != NULL && right != NULL) {
            if (left->val < right->val){
                cur->next = left;
                left = left->next;
            }else {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = left ? left : right;
        ListNode* ret = fake->next;
        delete fake;
        return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* fakeHead = new ListNode(0);
        fakeHead->next = NULL;
        ListNode* cur = head;
        while (cur != NULL) {
            ListNode* pre = fakeHead;
            int value = cur->val;
            while(pre->next != NULL && value > pre->next->val)
                pre = pre->next;
            ListNode* temp = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = temp;
        }
        return fakeHead->next;
    }
};