class Solution(object):
def duplicateInArray(self, nums):
l,r=1,len(nums)-1
while l<r:
ans=0
mid=(l+r)//2
for i in nums:
if l<=i<=mid:
ans+=1
if ans>mid-l+1:
r=mid
else:
l=mid+1
return l