func romanToInt(s string) int {
    hash := map[byte]int{
        'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}

    str := []byte(s)
    ans := 0
    for i := 0; i < len(str); i++ {
        if i < len(str)-1 && hash[str[i]] < hash[str[i+1]] {
            ans -= hash[str[i]]
        } else {
            ans += hash[str[i]]
        }
    }
    return ans
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > q->val) swap(p, q);
        if (!root) return nullptr;
        // cout << root->val << endl;
        if (p->val <= root->val && root->val <= q->val) return root;
        if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        return lowestCommonAncestor(root->left, p, q);
    }
};

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        if (arr.size() < 3) return false;
        for (int i = 0; i < arr.size() - 2; i++) {
            if ((arr[i] & 1) && (arr[i+1] & 1) && (arr[i+2] & 1)) {
                return true;
            } 
        }
        return false;
    }
};

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        if (arr.size() < 3) return false;
        for (int i = 0; i < arr.size() - 2; i++) {
            if ((arr[i] & 1) && (arr[i+1] & 1) && (arr[i+2] & 1)) {
                return true;
            } 
        }
        return false;
    }
};

class Solution {
public:
    int minOperations(int n) {
        vector<int> nums(n);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = 2 * i + 1;
            sum += nums[i];
        }
        int target = sum / n;
        int ans = 0;
        for (int i = 0; i < n ; i++) {
            if (target < nums[i]) ans += abs(target-nums[i]);
            // cout << ans << endl;
        }

        return ans;
    }
};

class Solution {
public:
    bool check(vector<int>& pos, int len, int m) {
        int cnt = 1;
        int t = pos[0];
        for (int i = 1; i < pos.size(); i++) {
            if (pos[i] - t >= len) {
                t = pos[i];
                cnt++;
                if (cnt >= m) break;
            }
        }
        return cnt >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int l = 1, r = position[position.size()-1];
        int ans = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if (check(position, mid, m)) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

class Solution {
public:
    unordered_map<int, int> dp;
    int dfs(int n) {
        if (n == 1) return 1;
        if (n == 2 || n == 3) return 2;
        // if (dp.count(n)) return dp[n];
        auto it = dp.find(n);
        if (it != dp.end()) return it->second;
        return dp[n] = min(dfs(n/2) + (n % 2) + 1, dfs(n/3) + (n % 3) + 1);
    }
    int minDays(int n) {
        // dp.clear();
        return dfs(n);
    }
};

class Solution {
public:
    bool check(vector<int>& pos, int len, int m) {
        int cnt = 1;
        int t = pos[0];
        for (int i = 1; i < pos.size(); i++) {
            if (pos[i] - t >= len) {
                t = pos[i];
                cnt++;
                if (cnt >= m) break;
            }
        }
        return cnt >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int l = 1, r = position[position.size()-1];
        int ans = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if (check(position, mid, m)) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
    if (root == nil || root == p || root == q) {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}