# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.lSum = 0    
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        self.convertBST(root.right)
        self.lSum += root.val
        root.val = self.lSum
        self.convertBST(root.left)
        return root

class Solution:
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return list(set(range(1, len(nums) + 1)) - set(nums))

class Solution:
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in range(len(nums)):
            idx = abs(nums[i]) - 1
            nums[idx] = - abs(nums[idx])
            #print(i, idx, nums)
            
        return [i + 1 for i in range(len(nums)) if nums[i] > 0]

class Solution:
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        return sum(s[i:j] == s[i:j][::-1] for j in range(len(s) + 1) for i in range(j))

class Solution:
    def countSubstrings(self, S):
        """
        :type s: str
        :rtype: int
        """
        N = len(S)
        ans = 0
        for center in range(2*N - 1):
            left = center // 2
            right = left + center % 2
            while left >= 0 and right < N and S[left] == S[right]:
                ans += 1
                left -= 1
                right += 1
        return ans

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        if not people:
            return []
        n = len(people)
        people_sorted = sorted(people, key = lambda x: (-x[0],x[1]))
        res = [people_sorted[0]]
        for i in range(1,n):
            hi, ki = people_sorted[i]
            res.insert(ki, people_sorted[i])
        return res

class Solution:
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        res = [0]
        for i in range(1, num + 1):
            res.append(res[i >> 1] + (i & 1))
        return res