#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

pair<int, int> findZeroSumSubarrayWithMostRepeatedElement(const vector<int>& arr) {
    unordered_map<int, int> prefixSumMap; // Maps prefix sum to index
    unordered_map<int, int> globalFreq;  // Tracks global element frequency
    int prefixSum = 0, maxFreq = 0, mostRepeatedElement = arr[0];
    
    prefixSumMap[0] = -1; // Handles cases where subarray starts at index 0
    
    for (int i = 0; i < arr.size(); i++) {
        prefixSum += arr[i];

        if (prefixSumMap.find(prefixSum) != prefixSumMap.end()) {
            int startIdx = prefixSumMap[prefixSum] + 1;

            // Update frequency for the elements in the new valid subarray
            for (int j = startIdx; j <= i; j++) {
                globalFreq[arr[j]]++;
                if (globalFreq[arr[j]] > maxFreq) {
                    maxFreq = globalFreq[arr[j]];
                    mostRepeatedElement = arr[j];
                }
            }
        } else {
            prefixSumMap[prefixSum] = i;
        }
    }

    return {mostRepeatedElement, maxFreq};
}

int main() {
    vector<int> arr = {1, 1, -1, 0, 0, 1, 0, -1, -1, -1, 0, 1, 0, 0, 1, 1, 0, 0, -1, -1};

    auto [mostRepeatedElement, mostRepeatedCount] = findZeroSumSubarrayWithMostRepeatedElement(arr);

    cout << "Most Repeated Element in Zero-Sum Subarray: " << mostRepeatedElement 
         << " (Repeated " << mostRepeatedCount << " times)" << endl;

    return 0;
}