Skip to content

Instantly share code, notes, and snippets.

@surinoel
Created November 15, 2019 10:02
Show Gist options
  • Save surinoel/d05a39aa8fc4009244c341296024f1a0 to your computer and use it in GitHub Desktop.
Save surinoel/d05a39aa8fc4009244c341296024f1a0 to your computer and use it in GitHub Desktop.
#include <stack>
#include <utility>
#include <iostream>
using namespace std;
int arr[1000001];
int cnt[1000001];
int ans[1000001];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
cnt[arr[i]] += 1;
}
stack<pair<int, int>> st;
for (int i = n; i >= 1; i--) {
while (!st.empty() && cnt[arr[i]] >= st.top().first) {
st.pop();
}
if (st.empty()) {
ans[i] = -1;
}
else {
ans[i] = st.top().second;
}
st.push(make_pair(cnt[arr[i]], arr[i]));
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment