int singleNonDuplicate(vector<int>& arr)
{
	int n = arr.size();
	if(n==1) return arr[0];
	if(arr[0]!=arr[1]) return arr[0];
	if(arr[n-1]!=arr[n-2]) return arr[n-1];

	int low=1;
	int high=n-2;

	while(low<=high){
		int mid=(low+high)/2;
		if(arr[mid]!=arr[mid-1] && arr[mid]!=arr[mid+1]){	//single element
			return arr[mid];
		}
		if(mid%2==1 && arr[mid-1]==arr[mid] || mid%2==0 && arr[mid+1]==arr[mid]){	//odd index
			low=mid+1;
		}
		else{	//even index
			high=mid-1;
		}
	}
	return -1;
}