# your code goes here
class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0
        h = len(nums)-1
 
        while(l<h):
            mid = (l+h)//2
            if mid % 2 == 1:
                mid = mid-1
 
            if nums[mid] == nums[mid+1]:
                l = mid + 2
            else:
                h = mid
 
        return nums[l]
 

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmNsYXNzIFNvbHV0aW9uKG9iamVjdCk6CiAgICBkZWYgc2luZ2xlTm9uRHVwbGljYXRlKHNlbGYsIG51bXMpOgogICAgICAgICIiIgogICAgICAgIDp0eXBlIG51bXM6IExpc3RbaW50XQogICAgICAgIDpydHlwZTogaW50CiAgICAgICAgIiIiCiAgICAgICAgbCA9IDAKICAgICAgICBoID0gbGVuKG51bXMpLTEKCiAgICAgICAgd2hpbGUobDxoKToKICAgICAgICAgICAgbWlkID0gKGwraCkvLzIKICAgICAgICAgICAgaWYgbWlkICUgMiA9PSAxOgogICAgICAgICAgICAgICAgbWlkID0gbWlkLTEKCiAgICAgICAgICAgIGlmIG51bXNbbWlkXSA9PSBudW1zW21pZCsxXToKICAgICAgICAgICAgICAgIGwgPSBtaWQgKyAyCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBoID0gbWlkCiAgICAgICAgCiAgICAgICAgcmV0dXJuIG51bXNbbF0KICAgICAgICA=