long maxModSum = 0;
long currentSum = 0;

// SortedSet to store prefix sums modulo k
SortedSet<long> modSet = new SortedSet<long>();
modSet.Add(0);

foreach (long num in a)
{
    currentSum = (currentSum + num) % k;
    maxModSum = Math.Max(maxModSum, currentSum);

    // Find the smallest prefix greater than currentSum
    var higher = modSet.GetViewBetween(currentSum + 1, k).Min;
    if (higher != default(long))
    {
        maxModSum = Math.Max(maxModSum, (currentSum - higher + k) % k);
    }

    modSet.Add(currentSum);
}

return maxModSum;