mtmatt.Page

void countSwaps(vector<int> a) {
    int ct=0;
    for(int i=0;i<a.size();i++){
        for (int j=0;j<a.size()-1;j++){
            if (a[j]>a[j+1]){
                ct++;
                swap(a[j],a[j+1]);
            }
        }
    }
    cout<<"Array is sorted in "<<ct<<" swaps."<<"\n";
    cout<<"First Element: "<<a[0]<<"\n";
    cout<<"Last Element: "<<a[a.size()-1];
    return;
}

int maximumToys(vector<int> ps, int k){
    sort(ps.begin(),ps.end());
    int sum=0,ct=0;
    for(auto a:ps){
        if(sum+a<k){
            sum+=a;
            ct++;
        }else break;
    }
    return ct;
}

vector<int> rotLeft(vector<int> a, int d) {
    vector<int> ans;

    int pos=d%a.size();
    for(int i=0;i<a.size();i++){
        ans.push_back(a[pos]);
        pos++;
        pos%=a.size();
    }
    return ans;
}

int hourglassSum(vector<vector<int>> arr) {
    int mx=-0x3f3f3f3f;
    for(int i=0;i<arr.size()-2;i++){
        for(int j=0;j<arr[i].size()-2;j++){
            int sum=arr[i][j]+
                    arr[i][j+1]+
                    arr[i][j+2]+
                    arr[i+1][j+1]+
                    arr[i+2][j]+
                    arr[i+2][j+1]+
                    arr[i+2][j+2];
            mx=max(mx,sum);
        }
    }
    return mx;
}

void minimumBribes(vector<int> q){
    int ans=0;
    for(int i=q.size()-1;i>=0;i--) {
        if(q[i]-(i+1)>2){
            cout<<"Too chaotic\n";
            return;
        }
        for(int j=max(0,q[i]-2);j<i;j++)
            if(q[j]>q[i])ans++;
    }
    cout<<ans<<"\n";
}

int minimumSwaps(vector<int> arr) {
    vector<int> o(arr);
    sort(o.begin(),o.end());
    int ct=0,update=0;
    int m[100010]{0};
    for(int i=0;i<arr.size();i++){
        if(arr[i]!=o[i]){
            swap(arr[i],arr[arr[i]-1]);
            ct++;
            i--;
        }
    }
    return ct;
}

struct edge{
    int s,e,c;
};

long arrayManipulation(int n, vector<edge> q) {
    long mx=0,now=0;
    sort(q.begin(),q.end(),[](edge a,edge b){
        return a.s<b.s;
    });
    vector<edge> bk(q);
    sort(bk.begin(),bk.end(),[](edge a,edge b){
        return a.e<b.e;
    });

    int i=0;
    for(auto a:q){
        now+=a.c;
        while(i<q.size() && a.s>bk[i].e){
            now-=bk[i].c;
            i++;
        }
        mx=max(mx,now);
    }
    return mx;
}

void checkMagazine(vector<string> magazine, vector<string> note) {
    unordered_map<string,int> m,n;
    for(auto a:magazine){
        m[a]++;
    }
    for(auto a:note){
        n[a]++;
    }

    for(auto a:n){
        if(m[a.first]<n[a.first]){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
}

int sherlockAndAnagrams(string s) {
    int ct=0,len=s.size();
    for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){
            multiset<char> st,tt;
            for(int k=i;k<=j;k++){
                st.insert(s[k]);
                tt.insert(s[k]);
            }

            for(int k=i+1;k<len-(j-i);k++){
                tt.insert(s[k+(j-i)]);
                auto it=tt.find(s[k-1]);
                if(it!=tt.end()) tt.erase(it);
                if(tt==st) ct++;
            }
        }
    }
    return ct;
}

string twoStrings(string s1, string s2) {
    unordered_set<char> s;
    for(auto a:s1){
        s.insert(a);
    }
    for(auto a:s2){
        if(s.count(a)){
            return "YES";
        }
    }
    return "NO";
}