int maxDepth(string s) {

    int currentMax =0;

    int maxi = 0;

    for(int i=0;i<s.size();i++){

        if(s[i]=='(') currentMax++;

        maxi = max(maxi,currentMax);

        if(s[i]==')') 

        currentMax--;

    }

    return maxi;

}

#include<bits/stdc++.h>

bool canWePlace(vector<int> &stalls, int dist, int cows){

    int cntCows=1, last=stalls[0];

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

        if(stalls[i]-last>=dist){

            cntCows++;

            last = stalls[i];

        }

        if(cntCows>=cows) return true;

    }

    return false;

}

int aggressiveCows(vector<int> &stalls, int k)

{

    sort(stalls.begin(), stalls.end());

    int n = stalls.size();

    int low=1, high=stalls[n-1]- stalls[0];

    while(low<=high){

        int mid = (low+high)/2;

        if(canWePlace(stalls,mid,k)== true) low=mid+1;

        else high=mid-1;

    }

    return high;

}

#include<bits/stdc++.h>

int cntStudent(vector<int>&arr, int pages){

    int student = 1;

    long long pageStu = 0;

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

        if(pageStu+arr[i]<=pages) pageStu += arr[i];

        else{

            student += 1;

            pageStu = arr[i];

        }

    }

    return student;

}

int findPages(vector<int>& arr, int n, int m) {

if(m>n) return -1;

int low = *max_element(arr.begin(),arr.end());

int high = accumulate(arr.begin(),arr.end(),0);

while(low<=high){

    int mid = (low+high)/2;

    int students = cntStudent(arr,mid);

    if(students>m) low = mid+1;

    else high = mid-1;

}

return low;

}

bool searchInARotatedSortedArrayII(vector<int>&arr, int k) {

 int n = arr.size(); // size of the array.

    int low = 0, high = n - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        //if mid points the target

        if (arr[mid] == k) return true;

        //Edge case:

        if (arr[low] == arr[mid] && arr[mid] == arr[high]) {

            low = low + 1;

            high = high - 1;

            continue;

        }

        //if left part is sorted:

        if (arr[low] <= arr[mid]) {

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

                //element exists:

                high = mid - 1;

            }

            else {

                //element does not exist:

                low = mid + 1;

            }

        }

        else { //if right part is sorted:

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

                //element exists:

                low = mid + 1;

            }

            else {

                //element does not exist:

                high = mid - 1;

            }

        }

    }

    return false;

}

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, high = n - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        //if mid points the target

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

        //if left part is sorted:

        if (arr[low] <= arr[mid]) {

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

                //element exists:

                high = mid - 1;

            }

            else {

                //element does not exist:

                low = mid + 1;

            }

        }

        else { //if right part is sorted:

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

                //element exists:

                low = mid + 1;

            }

            else {

                //element does not exist:

                high = mid - 1;

            }

        }

    }

    return -1;

}

#include <bits/stdc++.h> 

int firstOcc(vector<int>& arr, int n, int k){

int low = 0, high=n-1,first=-1;

while(low<=high){

int mid = (low + high)/2;

if(arr[mid]==k){

    first = mid;

    high = mid-1;

}

else if(arr[mid]<k) low=mid+1;

else high = mid-1;

}

return first;

}

int lastOcc(vector<int>& arr, int n, int k){

int low = 0, high=n-1,last=-1;

while(low<=high){

int mid = (low + high)/2;

if(arr[mid]==k){

    last = mid;

    low = mid+1;

}

else if(arr[mid]<k) low=mid+1;

else high = mid-1;

}

return last;

}

pair<int, int> firstAndLastPosition(vector<int>& arr, int n, int k)

{

 int first = firstOcc(arr,n,k);

 if(first==-1) return {-1,-1};

 int last = lastOcc(arr,n,k);

 return {first, last};

}

#include <bits/stdc++.h>

int merge(vector<int> &arr, int low, int mid, int high) {

    vector<int> temp; // temporary array

    int left = low;      // starting index of left half of arr

    int right = mid + 1;   // starting index of right half of arr

    //Modification 1: cnt variable to count the pairs:

    int cnt = 0;

    //storing elements in the temporary array in a sorted manner//

    while (left <= mid && right <= high) {

        if (arr[left] <= arr[right]) {

            temp.push_back(arr[left]);

            left++;

        }

        else {

            temp.push_back(arr[right]);

            cnt += (mid - left + 1); //Modification 2

            right++;

        }

    }

    // if elements on the left half are still left //

    while (left <= mid) {

        temp.push_back(arr[left]);

        left++;

    }

    //  if elements on the right half are still left //

    while (right <= high) {

        temp.push_back(arr[right]);

        right++;

    }

    // transfering all elements from temporary to arr //

    for (int i = low; i <= high; i++) {

        arr[i] = temp[i - low];

    }

    return cnt; // Modification 3

}

int mergeSort(vector<int> &arr, int low, int high) {

    int cnt = 0;

    if (low >= high) return cnt;

    int mid = (low + high) / 2 ;

    cnt += mergeSort(arr, low, mid);  // left half

    cnt += mergeSort(arr, mid + 1, high); // right half

    cnt += merge(arr, low, mid, high);  // merging sorted halves

    return cnt;

}

int numberOfInversions(vector<int>&a, int n) {

    // Count the number of pairs:

    return mergeSort(a, 0, n - 1);

}

#include<bits/stdc++.h>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    int n=arr.size();

    vector<vector<int>> ans;

    sort(arr.begin(),arr.end());

    for(int i=0;i<n;i++){

        int start = arr[i][0];

        int end = arr[i][1];

        if(!ans.empty() && end<=ans.back()[1]) continue;

        for(int j=i+1;j<n;j++){

            if(arr[j][0]<=end)

            end = max(end,arr[j][1]);

            else break;

        }

        ans.push_back({start ,end});

    }

return ans;

}

#include<bits/stdc++.h>

int subarraysWithSumK(vector < int > a, int b) {

    int xr =0, cnt=0;

    unordered_map<int,int> mpp;

    mpp[xr]++ ;// for {0,1}

    for(int i=0;i<a.size();i++){

        xr = xr ^ a[i];

        int x = xr ^ b;

        cnt += mpp[x];

        mpp[xr]++;

    }

    return cnt;

}

#include <bits/stdc++.h>

vector<vector<int>> fourSum(vector<int>& nums, int target) {

    int n = nums.size();

    sort(nums.begin(),nums.end());

    vector<vector<int>> ans;

    for(int i=0;i<n;i++){

        if(i>0 && nums[i]==nums[i-1]) continue;

    for(int j=i+1;j<n;j++){

        if(j!=i+1 && nums[j]==nums[j-1]) continue;

        int k = j+1;

        int l = n-1;

        while(k<l){

            long long sum = nums[i]+nums[j];

            sum += nums[k];

            sum += nums[l];

            if(sum==target){

              vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};

              ans.push_back(temp);

              k++, l--;

              while (k < l && nums[k] == nums[k - 1])k++;

              while(k<l && nums[l]==nums[l+1]) l--;

        }

        else if(sum<target) k++;

        else l--;

        }

    }

    }

    return ans;

}