public int SubarraySum(int[] nums, int k) {
    var prefixMap = new Dictionary<int, int> { [0] = 1 };
    int currSum = 0, count = 0;
    foreach (int x in nums) {
        currSum += x;
        if (prefixMap.TryGetValue(currSum - k, out int freq)) {
            count += freq;
        }
        prefixMap[currSum] = prefixMap.GetValueOrDefault(currSum, 0) + 1;
    }
    return count;
}

public int MinEatingSpeed(int[] piles, int h) {
    bool CanFinish(int speed) {
        long totalHours = 0;
        foreach (int p in piles) {
            totalHours += (p + speed - 1L) / speed; // Ceiling division
        }
        return totalHours <= h;
    }

    int low = 1, high = piles.Max();
    int ans = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (CanFinish(mid)) {
            ans = mid;
            high = mid - 1; // Feasible! Try finding a smaller speed
        } else {
            low = mid + 1;  // Too slow, increase speed
        }
    }
    return ans;
}

public int[] DailyTemperatures(int[] temperatures) {
    int n = temperatures.Length;
    var res = new int[n];
    var stack = new Stack<int>(); // Stores indices
    
    for (int i = 0; i < n; i++) {
        while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
            int prevIdx = stack.Pop();
            res[prevIdx] = i - prevIdx;
        }
        stack.Push(i);
    }
    return res;
}

public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    var left = LowestCommonAncestor(root.left, p, q);
    var right = LowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root; // Split point
    return left ?? right;
}

public class TrieNode {
    public Dictionary<char, TrieNode> Children = new();
    public bool IsWord = false;
}

public class Trie {
    private readonly TrieNode _root = new();

    public void Insert(string word) {
        var node = _root;
        foreach (char c in word) {
            if (!node.Children.ContainsKey(c)) node.Children[c] = new TrieNode();
            node = node.Children[c];
        }
        node.IsWord = true;
    }

    public bool StartsWith(string prefix) {
        var node = _root;
        foreach (char c in prefix) {
            if (!node.Children.TryGetValue(c, out node)) return false;
        }
        return true;
    }
}

public class UnionFind {
    private readonly int[] _parent;
    private readonly int[] _rank;

    public UnionFind(int n) {
        _parent = new int[n];
        _rank = new int[n];
        for (int i = 0; i < n; i++) { _parent[i] = i; _rank[i] = 1; }
    }

    public int Find(int i) {
        if (_parent[i] != i) {
            _parent[i] = Find(_parent[i]); // Path compression
        }
        return _parent[i];
    }

    public bool Union(int i, int j) {
        int rootI = Find(i), rootJ = Find(j);
        if (rootI == rootJ) return false; // Cycle detected!
        if (_rank[rootI] < _rank[rootJ]) (rootI, rootJ) = (rootJ, rootI);
        _parent[rootJ] = rootI;
        _rank[rootI] += _rank[rootJ];
        return true;
    }
}

public int CoinChange(int[] coins, int amount) {
    var dp = new int[amount + 1];
    Array.Fill(dp, amount + 1); // Sentinel max value
    dp[0] = 0;
    
    for (int a = 1; a <= amount; a++) {
        foreach (int c in coins) {
            if (a - c >= 0) {
                dp[a] = Math.Min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

public class BoundedBlockingQueue {
    private readonly Queue<int> _queue = new();
    private readonly int _capacity;
    private readonly object _lock = new();

    public BoundedBlockingQueue(int capacity) { _capacity = capacity; }

    public void Enqueue(int element) {
        lock (_lock) {
            while (_queue.Count == _capacity) {
                Monitor.Wait(_lock); // Handle spurious wakeups
            }
            _queue.Enqueue(element);
            Monitor.PulseAll(_lock);
        }
    }

    public int Dequeue() {
        lock (_lock) {
            while (_queue.Count == 0) {
                Monitor.Wait(_lock);
            }
            int item = _queue.Dequeue();
            Monitor.PulseAll(_lock);
            return item;
        }
    }
}