#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
vector<int> tree[MAXN];
vector<int> prefixSum;
vector<int> cost;
vector<int> parent;
int N, K;
void dfs(int node, int par, int currentSum) {
    prefixSum[node] = currentSum + cost[node];
    parent[node] = par;
    for (int child : tree[node]) {
        if (child != par) {
            dfs(child, node, prefixSum[node]);
        }
    }
}
int solve(int N, int K, vector<int>& A, vector<vector<int>>& edges) {
    cost = A;
    prefixSum.assign(N, 0);
    parent.assign(N, -1);
    
    for (int i = 0; i < N; ++i) {
        tree[i].clear();
    }
    
    for (auto& edge : edges) {
        int u = edge[0] - 1;
        int v = edge[1] - 1;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(0, -1, 0);
    int maxCandies = 0;
    for (int i = 0; i < N; ++i) {
        int remainingMoney = K;
        int candies = 0;
        for (int j = i; j != -1; j = parent[j]) {
            if (remainingMoney >= cost[j]) {
                remainingMoney -= cost[j];
                candies++;
            } else {
                break;
            }
        }
        maxCandies = max(maxCandies, candies);
    }

    return maxCandies;
}

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int solve(int N, int K, const vector<int>& houses) {
    unordered_map<int, int> houseIndex;
    for (int i = 0; i < houses.size(); ++i) {
        houseIndex[houses[i] - 1] = i + 1;
    }

    priority_queue<int> pq;
    for (int i = 0; i < K; ++i) {
        pq.push(houseIndex[i]);
    }

    int ans = pq.top();
    for (int i = 1; i + K - 1 < N; ++i) {
        pq.push(houseIndex[i + K - 1]);
        while (!pq.empty() && pq.top() > houseIndex[i + K - 1]) {
            pq.pop();
        }
        ans = min(ans, pq.top());
    }

    return ans;
}

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> smallestLexicographicalSubsequence(vector<int>& hubs, int k) {
    vector<int> result;
    stack<int> st;
    int n = hubs.size();

    for (int i = 0; i < n; ++i) {
        while (!st.empty() && st.top() > hubs[i] && st.size() + (n - i) > k) {
            st.pop();
        }
        if (st.size() < k) {
            st.push(hubs[i]);
        }
    }
        while (!st.empty()) {
        result.insert(result.begin(), st.top());
        st.pop();
    }
    
    return result;
}

SELECT 
    i.invoice_number,
    c.customer_name,
    COUNT(co.id) AS number_of_contacts
FROM 
    customer c
JOIN 
    invoice i ON c.id = i.customer_id
LEFT JOIN 
    contact co ON c.id = co.customer_id AND co.contact_start_time < i.invoice_date
LEFT JOIN 
    user_account ua ON co.user_account_id = ua.id
WHERE 
    i.user_account_id NOT IN (
        SELECT DISTINCT user_account_id 
        FROM contact 
        WHERE customer_id = c.id AND contact_start_time < i.invoice_date
    )
GROUP BY 
    i.id, c.id
ORDER BY 
    i.invoice_number ASC

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int minimumPower(vector<int>& cells) {
    priority_queue<int, vector<int>, greater<int>> minHeap(cells.begin(), cells.end());
    
    int totalPower = 0;
        while (minHeap.size() > 1) {
        int first = minHeap.top();
        minHeap.pop();
        int second = minHeap.top();
        minHeap.pop();
        
        int power = first + second;
        totalPower += power;
        
        minHeap.push(power);
    }
    
    return totalPower;
}