Here is my Python solution!

def maximumSum(a, m):
    prefixes = [(0, -1)]
    for i in range(len(a)):
        prefixes.append(((prefixes[-1][0] + a[i]) % m, i))
    prefixes.sort()
    maximum = prefixes[-1][0]
    for (a, i1), (b, i2) in zip(prefixes[:-1], prefixes[1:]):
        if b > a and i1 > i2:
            maximum = max(maximum, (a - b) % m)
    return maximum

No need to use tree or sorted set. Just store all the prefix sums and sort. This idea comes from a different problem of minimising loss on house purchasing.

def maximumSum(a, m):
    n = len(a)
    prefix_sums = [(a[0]%m,0)]
    for i in range(1,n):
        new_sum = a[i] + prefix_sums[i-1][0]
        prefix_sums.append((new_sum%m,i))
    prefix_sums.sort()
    max_sum = prefix_sums[-1][0]
    prev_index = prefix_sums[0][1]
    for i in range(1,n):
        if prefix_sums[i][0] == prefix_sums[i-1][0]:
            prev_index = max(prev_index, prefix_sums[i][1])
        else:
            if prefix_sums[i][1] < prev_index:
                max_sum = max(max_sum, prefix_sums[i-1][0] - prefix_sums[i][0] + m)
            prev_index = prefix_sums[i][1]
                
    return max_sum  

    q = int(input().

pure java... package geeksforgeeks; import java.util.*;

public class Maxnumber {

public static void main(String[] args) {
    int module, sum = 0, maxNumber = 0, start = 0, repeat = 2, sumofarray = 0, decrese = 1;
    Scanner sc = new Scanner(System.in);

    System.out.println("size");
    int n = sc.nextInt();
    int arr[] = new int[n];

    System.out.println("element");
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    System.out.println("modulo");
    module = sc.nextInt();

    // Sum of the whole array
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }

    int remainder = sum % module;
    maxNumber = Math.max(remainder, maxNumber);

    // Check subarrays with different lengths
    while (start != arr.length - 1) {
        int x = 0;
        int index = start;  // Start index for each iteration

        while (x != repeat && index < arr.length) {  // Prevent out of bounds
            for (int j = 0; j < decrese && index < arr.length; j++) {
                sumofarray += arr[index];
                index++;
            }
            remainder = (sum - sumofarray) % module;
            maxNumber = Math.max(remainder, maxNumber);
            sumofarray = 0;  // Reset sum for the next subarray
            x++;
        }
        start++;
        repeat++;
        decrese++;
    }

    System.out.println(maxNumber);

            (using array in java)...................



            sc.close();
}

}

pure java... package geeksforgeeks; import java.util.*;

public class Maxnumber {

public static void main(String[] args) {
    int module, sum = 0, maxNumber = 0, start = 0, repeat = 2, sumofarray = 0, decrese = 1;
    Scanner sc = new Scanner(System.in);

    System.out.println("size");
    int n = sc.nextInt();
    int arr[] = new int[n];

    System.out.println("element");
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    System.out.println("modulo");
    module = sc.nextInt();

    // Sum of the whole array
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }

    int remainder = sum % module;
    maxNumber = Math.max(remainder, maxNumber);

    // Check subarrays with different lengths
    while (start != arr.length - 1) {
        int x = 0;
        int index = start;  // Start index for each iteration

        while (x != repeat && index < arr.length) {  // Prevent out of bounds
            for (int j = 0; j < decrese && index < arr.length; j++) {
                sumofarray += arr[index];
                index++;
            }
            remainder = (sum - sumofarray) % module;
            maxNumber = Math.max(remainder, maxNumber);
            sumofarray = 0;  // Reset sum for the next subarray
            x++;
        }
        start++;
        repeat++;
        decrese++;
    }

    System.out.println(maxNumber);
    sc.close();
}

}

This is my idea

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;