vector<int> getFinalLocations(vector<int> locations, vector<int> movedFrom, vector<int> movedTo) {

    multiset<int> dataLocations(locations.begin(), locations.end());
    for (int i = 0; i < movedFrom.size(); ++i) {
        auto it = dataLocations.find(movedFrom[i]);
        if (it != dataLocations.end()) {
            dataLocations.erase(it);
        }
        dataLocations.insert(movedTo[i]);
    }
    vector<int> finalLocations(dataLocations.begin(), dataLocations.end());
    return finalLocations;
}

#include <bits/stdc++.h>
using namespace std;
int count_inversions(const string &s) {
    int n = s.size(), inv = 0;
    vector<int> freq(26, 0);
    for (int i = n - 1; i >= 0; --i) {
        int c = s[i] - 'a';
        for (int j = 0; j < c; ++j) inv += freq[j];
        freq[c]++;
    }
    return inv;
}

int getMinInversion(string s, string t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> cs(n + 1, vector<int>(26, 0)), ct(m + 1, vector<int>(26, 0));

    for (int i = 1; i <= n; ++i) {
        cs[i] = cs[i - 1];
        cs[i][s[i - 1] - 'a']++;
    }
    for (int j = 1; j <= m; ++j) {
        ct[j] = ct[j - 1];
        ct[j][t[j - 1] - 'a']++;
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i < n) {
                int inv = 0;
                for (int c = s[i] - 'a' + 1; c < 26; ++c) inv += ct[j][c];
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + inv);
            }
            if (j < m) {
                int inv = 0;
                for (int c = t[j] - 'a' + 1; c < 26; ++c) inv += cs[i][c];
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + inv);
            }
        }
    }

    int inv_s = count_inversions(s), inv_t = count_inversions(t);
    return dp[n][m] + inv_s + inv_t;
}

int solution(int n,vector<int>nums){
  priority_queue<long long, vector<long long>, greater<long long> > pq;
  long long S = 0;
  
  for(int i = 1;i <= n;i++){
    int x=nums[i-1];
    S += x;
    pq.push(x);
    
    while(S < 0){
      S -= pq.top();
      pq.pop();
    }
  }
  
  return (int) pq.size();
    }

class Solution {
public:
    int helper(vector<int> &nums, int k){
        int frequency = 0, ans = 0; ; 
        map<int, int> mapping; 
        for(int i = 0; i < nums.size(); ++i){
            ans += nums[i]; 
            if(ans == k){
                frequency++; 
            }
            if(mapping.find(ans - k) != mapping.end()){ 
                frequency += mapping[ans - k];
            }
            mapping[ans]++; 
        }
        return frequency;
    }
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int count = 0;
        for(int i = 0; i < matrix.size(); ++i){
            vector<int> result(matrix[0].size(), 0);
            for(int j = i; j < matrix.size(); ++j){ 
                for(int k = 0; k < matrix[0].size(); ++k){ 
                    result[k] += matrix[j][k];
                }
                count += helper(result, target);
            }
        }
        return count;
    }
};

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int minCost(int N, int X, int Y, vector<int>& happiness, vector<int>& weight, vector<int>& cost) {
    vector<vector<int>> dp(X + 1, vector<int>(Y + 1, INT_MAX));
    dp[0][0] = 0; 
    for (int i = 0; i < N; ++i) {
    for (int h = X; h >= 0; --h) {
    for (int w = Y; w >= weight[i]; --w) {
    if (dp[h][w - weight[i]] != INT_MAX) {
    int newH = min(X, h + happiness[i]);
    dp[newH][w] = min(dp[newH][w], dp[h][w - weight[i]] + cost[i]);
    }
    }
    }
    }
    int minCost = INT_MAX;
    for (int w = 0; w <= Y; ++w) {
        minCost = min(minCost, dp[X][w]);
    }

    return minCost;
}

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
void bfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (int neighbor : graph[node]) {
    if (!visited[neighbor]) {
    visited[neighbor] = true;
    q.push(neighbor);
            }
        }
    }
}
int solve(int N, vector<pair<int, int>>& friends) {
vector<vector<int>> graph(N + 1); 
for (auto& edge : friends) {
int u = edge.first, v = edge.second;
graph[u].push_back(v);
graph[v].push_back(u);
    }
vector<bool> visited(N + 1, false);
int components = 0;
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
bfs(i, graph, visited);
++components;
}
}
return components - 1;
}

import java.util.*;
public class Main {
    static int programmerStrings(String s) {
        String programmer = "programmer";
        String head = programmer;
        int i = 0;
        for (; i < s.length(); i++) {
            int pIndex = head.indexOf(s.charAt(i));
            if (pIndex != -1) {
                head = head.substring(0, pIndex) + head.substring(pIndex + 1);
            }

            if (head.length() == 0) {
                i++;
                break;
            }
        }
        String tail = programmer;
        int j = s.length() - 1;
        for (; j >= 0; j--) {
            int pIndex = tail.indexOf(s.charAt(j));
            if (pIndex != -1) {
                tail = tail.substring(0, pIndex) + tail.substring(pIndex + 1);
            }

            if (tail.length() == 0) {
                j--;
                break;
            }
        }

        return j - i + 1;
    }