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

using namespace std;

pair<vector<int>, pair<int, int>> findZeroSumSubarrayWithMostRepeatedElement(vector<int>& arr) {
    unordered_map<int, int> prefixSumMap; // Stores prefix sums and their first occurrence index
    int prefixSum = 0;
    int start = -1, end = -1;
    int maxFreq = 0, mostRepeatedElement = arr[0], mostRepeatedCount = 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 leftIndex = prefixSumMap[prefixSum] + 1;
            vector<int> subarray(arr.begin() + leftIndex, arr.begin() + i + 1);

            // Count element frequencies in this subarray
            unordered_map<int, int> tempFreq;
            for (int num : subarray) tempFreq[num]++;

            // Find the most frequent element
            for (auto& [num, freq] : tempFreq) {
                if (freq > maxFreq) {
                    maxFreq = freq;
                    mostRepeatedElement = num;
                    mostRepeatedCount = freq;
                    start = leftIndex;
                    end = i;
                }
            }
        } else {
            prefixSumMap[prefixSum] = i;
        }
    }

    vector<int> bestSubarray;
    if (start != -1) {
        bestSubarray.assign(arr.begin() + start, arr.begin() + end + 1);
    }

    return {bestSubarray, {mostRepeatedElement, mostRepeatedCount}};
}

int main() {
    vector<int> arr = {4, 2, -3, 1, 6, -3, 1, 3, -2, -1, 4, -4, 2};

    auto [subarray, elementInfo] = findZeroSumSubarrayWithMostRepeatedElement(arr);
    int mostRepeatedElement = elementInfo.first;
    int mostRepeatedCount = elementInfo.second;

    cout << "Optimal Zero-Sum Subarray: ";
    for (int num : subarray) cout << num << " ";
    cout << "\nMost Repeated Element: " << mostRepeatedElement 
         << " (Repeated " << mostRepeatedCount << " times)" << endl;

    return 0;
}