class Solution {
public:
    vector<int> duplicates(vector<int>& nums){
        unordered_set<int> uSet;
        int n = nums.size();
        vector<int> dup(n, 0);
        for(int i = 0 ; i < n ;i++){
            if(uSet.find(nums[i]) != uSet.end()){
                dup[i] = 1;
            }
            if(i != 0)
                dup[i] += dup[i-1];
            uSet.insert(nums[i]);
        }
        return dup;
    }
    int minOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int req = nums.size() - 1 , ans = nums.size() - 1, n =nums.size();
        vector<int> d = duplicates(nums);
        for(int ptr = 0; ptr < n-1 ;ptr++ ){
            int idx = lower_bound(nums.begin(), nums.end(), req + nums[ptr]) - nums.begin();
            if(idx < n ){
                int val = nums[ptr] + req;
                if(nums[idx] != val)
                    ans = min(ans, n - idx + ptr + d[idx] - d[ptr]);
                else
                    ans = min(ans, n - idx + ptr - 1 + d[idx] - d[ptr]);
            } 
            else
                ans = min(ans, d[n-1] - d[ptr]+ptr);
        }
        return ans;

    }
};

#include <stdio.h>  
int binarySearch(int a[], int beg, int end, int val)    
{    
    int mid;    
    if(end >= beg)     
    {        mid = (beg + end)/2;    
/* if the item to be searched is present at middle */  
        if(a[mid] == val)    
        {                 
            return mid+1;    
        }    
            /* if the item to be searched is smaller than middle, then it can only be in left subarray */  
        else if(a[mid] < val)     
        {  
            return binarySearch(a, mid+1, end, val);    
        }    
            /* if the item to be searched is greater than middle, then it can only be in right subarray */  
        else     
        {  
            return binarySearch(a, beg, mid-1, val);    
        }          
    }    
    return -1;     
}   
int main() {  
  int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array  
  int val = 40; // value to be searched  
  int n = sizeof(a) / sizeof(a[0]); // size of array  
  int res = binarySearch(a, 0, n-1, val); // Store result  
  printf("The elements of the array are - ");  
  for (int i = 0; i < n; i++)  
  printf("%d ", a[i]);   
  printf("\nElement to be searched is - %d", val);  
  if (res == -1)  
  printf("\nElement is not present in the array");  
  else  
  printf("\nElement is present at %d position of array", res);  
  return 0;  
}  

// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(arr[mid] == x)
				return mid;

			else if(arr[mid] > x)
				high = mid - 1;

			else
				low = mid + 1;
		}

		return -1;
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;

		int x = 25;
    
        System.out.println(bSearch(arr, n, x));  // Output : -1
		
    } 

}





// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(arr[mid] == x)
			return mid;

		else if(arr[mid] > x)
			return bSearch(arr, low, mid - 1, x);

		else
			return bSearch(arr, mid + 1, high, x);
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;

		int x = 20;

        System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
    } 
}

int firstOccurance(vector<int> &ar,int target){
  int low = 0,high = ar.size()-1,ans = -1;
  while(low<=high){
    int mid = low+(high-low)/2;
    
    if(ar[mid]==target){
      //mid can be our answer but we are not sure so reduce the search space
      ans = mid;
      high = mid-1;//for first occurance go to left
    }
    else if(ar[mid]>target)
      high = mid-1;
    else
      low = mid+1;
  }
  return ans;//if element is not present ans will remain -1,and will be returned as it is.
}

int lastOccurance(vector<int> &ar,int target){
  
  int low = 0,high = ar.size()-1,ans = -1;
  while(low<=high){
    int mid = low+(high-low)/2;
    
    if(ar[mid]==target){
      //mid can be our answer but we are not sure so reduce the search space
      ans = mid;
      low = mid+1; //for lasat occurance go to right
    }
    else if(ar[mid]>target)
      high = mid-1;
    else
      low = mid+1; 
  }
  
  return ans;//if element is not present ans will remain -1,and will be returned as it is.
}

//whenever there is sorted array first think of binary search

int binarySearch(vector<int> &ar, int target)
{

    int low = 0, high = ar.size() - 1;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;

        if (ar[mid] == target)
            return mid;
        else if (ar[mid] > target)
            high = mid - 1; // go to left
        else
            low = mid + 1; // go to right
    }

    return -1; // if element is not found
}

//the above solution is only ,if array is sorted in ascending order
//for descending sorted array condition's to go to left and right reverse

//time complexity :- O(logn);