int upperBound(vector<int> &arr, int n, int x) {

    // Write your code here

int low =0;

    int high=arr.size()-1;

    int ans=high+1;

  while(low<=high)

  {

      int mid=(low+high)/2;

      if(arr[mid]>x)

      {

          ans=mid;

          high=mid-1;

      }

      else {

          low=mid+1;

      }

  }

 return ans;

}

int search(vector<int>& arr, int n, int k)

{

    // Write your code here.

    // Return the position of K in ARR else return -1.

  int low =0;

  int high=n-1;

  while(low<=high)

  {

 int mid=(low+high)/2;

 if(arr[mid]==k)

 return mid;

 if(arr[low]<=arr[mid])//left sorted

{

    if(arr[mid]>=k && arr[low]<=k)

    {

        high=mid-1;

    }

    else  {

        low=mid+1;

    }

}

else

{

    if(arr[mid]<=k&& k<=arr[high])

    {

        low=mid+1;

    }

    else 

    high=mid-1;

}

  }

  return -1;

}

void selectionSort(vector<int>&arr) {

    // Write your code here.

 for(int i=0;i<arr.size()-1;i++){

    int min=arr[i];

    for (int j = i + 1; j < arr.size(); j++) {

      if (min > arr[j])

        min = arr[j];

    }

      swap(min, arr[i]);

 }

}

 void f(vector<int> &vec ,int n)

{

    if(n<1)

    return;

    vec.push_back(n);

    f(vec,n-1);

}

vector<int> printNos(int x) {

    // Write Your Code Here

    vector<int> ans;

    f(ans,x);

    return ans;

}

void f(vector<int> &vec ,int x,int start)

{

    if(x<start) return ;

    vec.push_back(start);

    f(vec,x,start+1);

}

vector<int> printNos(int x) {

    vector<int> ans;

    f(ans, x,1);

    return ans;

}

vector<int> printNos(int x) {

    vector<int> ans;

    if(x > 1)

        ans = printNos(x-1);

    ans.push_back(x);

    return ans; 

}