Problem 22: Maximum Subarray Sum Modulo

Problem Statement: Given an array of n integers and an integer m, find the maximum value of the sum of a subarray modulo m.

Input

The first line contains two integers n and m. The second line contains n space‐separated integers.

Output

Print the maximum subarray sum modulo m.

Examples


Input:
3 7
3 3 9

Output:
6

Solution Explanation

Method 1: Use prefix sums with a set to store previous prefix sums and for each prefix, find the smallest prefix greater than the current prefix to maximize the modulo difference. Method 2: Use a brute force approach by checking all subarrays which works for small arrays but is not efficient.

Solution in C++


#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m; cin >> n >> m;
    vector a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    set prefixSet;
    long long ans = 0, prefix = 0;
    prefixSet.insert(0);
    for (int i = 0; i < n; i++){
        prefix = (prefix + a[i]) % m;
        ans = max(ans, prefix);
        auto it = prefixSet.lower_bound(prefix + 1);
        if(it != prefixSet.end()){
            ans = max(ans, (prefix - *it + m) % m);
        }
        prefixSet.insert(prefix);
    }
    cout << ans << "
";
    return 0;
}