#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
void balanceHeaps(priority_queue<int>& maxHeap, priority_queue<int, vector<int>, greater<int>>& minHeap) {
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
int sequence(int N, vector<int> A) {
int maxOccurrences = 0;
for (int l = 0; l < N; ++l) {
unordered_map<int, int> freq;
priority_queue<int> maxHeap; // lower half
priority_queue<int, vector<int>, greater<int>> minHeap; // upper half
for (int r = l; r < N; ++r) {
int num = A[r];
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
balanceHeaps(maxHeap, minHeap);
freq[num]++;
int median1 = maxHeap.top();
int median2 = minHeap.empty() ? median1 : minHeap.top();
maxOccurrences = max(maxOccurrences, freq[median1]);
if (median1 != median2) {
maxOccurrences = max(maxOccurrences, freq[median2]);
}
}
}
return maxOccurrences;
}
