class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        while (nums.size() > 1 && nums.back() == nums[0]) nums.pop_back();
        if (nums[0] <= nums.back()) return nums[0];
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums[0] < nums.back()) return nums[0];
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

class Solution {
public:
    string reverseWords(string s) {
        while (s[0] == ' ') s.erase(s.begin());
        while (s.back() == ' ') s.pop_back();
        for (int i = 0; i < s.size(); i ++ ) {
            int j = i;
            while (s[j] == ' ') s.erase(s.begin() + j);
            while (j < s.size() && s[j] != ' ') j ++;
            reverse(s.begin() + i, s.begin() + j);
            i = j;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};

class Solution {
public:
    unordered_set<string> S;
    vector<string> res, path;

    void dfs(string s) {
        if (s == "") {
            string ans = "";
            for (int i = 0; i < path.size(); i ++ ) {
                ans += path[i];
                if (i != path.size() - 1) ans += " ";
            }
            res.push_back(ans);
            return;
        }
        for (int i = 1; i <= s.size(); i ++ ) {
            auto t = s.substr(0, i);
            if (S.count(t)) {
                path.push_back(t);
                dfs(s.substr(i));
                path.pop_back();
            }
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        S = unordered_set<string>(wordDict.begin(), wordDict.end());
        dfs(s);
        return res;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        for (auto p = head; p; p = p->next->next) {
            auto q = new Node(p->val);
            q->next = p->next;
            p->next = q;
        }
        for (auto p = head; p; p = p->next->next) {
            if (p->random) {
                p->next->random = p->random->next;
            }
        }
        auto dummy = new Node(0);
        for (Node *p = head, *q = dummy; p; p = p->next) {
            q->next = p->next;
            q = q->next;
            p->next = q->next;
        }
        return dummy->next;
    }
};

class Solution {
public:
// 1221121221
// 1 2 211 2
    int magicalString(int n) {
        string s = "122";
        int i = 2;
        char c = '1';
        while (s.size() < n) {
            if (s[i] == '2') s.push_back(c);
            s.push_back(c);
            if (c == '2') c = '1';
            else c = '2';
            i ++;
        }
        int res = 0;
        for (int i = 0; i < n; i ++ )
            if (s[i] == '1')
                res ++;
        return res;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i ++ ) {
            int one = 0;
            for (auto x : nums)
                if (x >> i & 1)
                    one ++;
            res += (one % 3) << i;
        }
        return res;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto x : nums) res ^= x;
        return res;
    }
};

class Solution {
public:
    int n;
    vector<int> f;
    vector<int> w;
    int candy(vector<int>& ratings) {
        n = ratings.size();
        f.resize(n, -1);
        w = ratings;

        int res = 0;
        for (int i = 0; i < n; i ++ ) res += dp(i);

        return res;
    }

    int dp(int x) {
        if (f[x] != -1) return f[x];
        f[x] = 1;
        if (x && w[x - 1] < w[x]) f[x] = max(dp(x - 1) + 1, f[x]);
        if (x + 1 < n && w[x + 1] < w[x]) f[x] = max(dp(x + 1) + 1, f[x]);
        return f[x];
    }
};