class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0, curr = 1, ans = 0;
        char[] sArray = s.toCharArray();
        for (int i = 1; i < sArray.length; i++) {
            if (sArray[i] == sArray[i - 1]) {
                curr += 1;
            } else {
                ans += Math.min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        ans += Math.min(prev, curr);
        return ans;
    }
}

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        int ans = 0;
        for (NestedInteger e : nestedList) {
            ans += helper(e, 1);
        }
        return ans;
    }

    private int helper(NestedInteger nested, int depth) {
        int ans = 0;
        if (nested.isInteger()) {
            ans += nested.getInteger() * depth;
        } else {
            List<NestedInteger> list = nested.getList();
            for (NestedInteger e : list) {
                ans += helper(e, depth + 1);
            }
        }
        return ans;
    }
}

public class ZigzagIterator {
    private int ptrOne, ptrTwo;
    private List<Integer> list1;
    private List<Integer> list2;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        list1 = v1;
        list2 = v2;
    }

    public int next() {
        if (ptrOne == list1.size()) {
            return list2.get(ptrTwo++);
        }
        if (ptrTwo == list2.size()) {
            return list1.get(ptrOne++);
        }
        if ((ptrOne + ptrTwo) % 2 == 0) {
            return list1.get(ptrOne++);
        } else {
            return list2.get(ptrTwo++);
        }
    }

    public boolean hasNext() {
        return ptrOne + ptrTwo < list1.size() + list2.size();
    }
}

class Solution {
    private int ans;

    public int countUnivalSubtrees(TreeNode root) {
        if (root != null) {
            helper(root);
        }
        return ans;
    }

    private int helper(TreeNode node) {
        int leftTree = node.left == null ? node.val : helper(node.left);
        int rightTree = node.right == null ? node.val : helper(node.right);
        if (node.val == leftTree && node.val == rightTree) {
            ans += 1;
            return node.val;
        }
        return -2000;
    }
}

class BSTIterator {
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        loadNodes(root);
    }

    public int next() {
        TreeNode topNode = stack.pop();
        if (topNode.right != null) {
            loadNodes(topNode.right);
        }
        return topNode.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    private void loadNodes(TreeNode node) {
        TreeNode ptr = node;
        while (ptr != null) {
            stack.push(ptr);
            ptr = ptr.left;
        }
    }
}

class Solution {
    public int candy(int[] ratings) {
        if (ratings.length == 0) {
            return 0;
        }
        int[] ans = new int[ratings.length];
        Arrays.fill(ans, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                ans[i] = ans[i - 1] + 1;
            }
        }
        int result = ans[ans.length - 1];
        for (int i = ans.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                ans[i] = Math.max(ans[i], ans[i + 1] + 1);
            }
            result += ans[i];
        }
        return result;
    }
}

class Solution {
    private int ans = 0;
    private int oddCount = 0;

    public int pseudoPalindromicPaths(TreeNode root) {
        helper(root, new int[10]);
        return ans;
    }

    private void helper(TreeNode node, int[] numCount) {
        if (node == null) {
            return;
        }
        int offset = numCount[node.val] % 2 == 1 ? -1 : 1;
        numCount[node.val] += 1;
        oddCount += offset;
        helper(node.left, numCount);
        helper(node.right, numCount);
        if (node.left == null && node.right == null && oddCount <= 1) {
            ans += 1;
        }
        numCount[node.val] -= 1;
        oddCount -= offset;
    }
}

class Solution {
    public List<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }

    private List<TreeNode> helper(int left, int right) {
        List<TreeNode> ans = new ArrayList<>();
        if (left > right) {
            ans.add(null);
            return ans;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftSubList = helper(left, i - 1);
            List<TreeNode> rightSubList = helper(i + 1, right);
            for (TreeNode leftSub : leftSubList) {
                for (TreeNode rightSub : rightSubList) {
                    TreeNode currRoot = new TreeNode(i);
                    currRoot.left = leftSub;
                    currRoot.right = rightSub;
                    ans.add(currRoot);
                }

            }
        }
        return ans;
    }
}

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[left] || target == nums[right] || target == nums[mid]) {
                return true;
            }
            if ((nums[mid] < nums[left] && target < nums[left]) || (nums[mid] > nums[left] && target > nums[left])) {
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                while (left < right && nums[left] == nums[left + 1])
                    left += 1;
                while (left < right && nums[right] == nums[right - 1])
                    right -= 1;
                left += 1;
                right -= 1;
            }
        }
        return false;
    }
}

class Solution {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0 || numRows <= 1) {
            return s;
        }
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < rows.length; i++) {
            rows[i] = new StringBuilder();
        }
        char[] sArray = s.toCharArray();
        boolean down = true;
        for (int i = 0, row = 0; i < sArray.length; i++) {
            rows[row].append(sArray[i]);
            if (down) {
                if (row == rows.length - 1) {
                    row -= 1;
                    down = false;
                } else {
                    row += 1;
                }
            } else {
                if (row == 0) {
                    row += 1;
                    down = true;
                } else {
                    row -= 1;
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder row : rows) {
            ans.append(row);
        }
        return ans.toString();
    }
}