Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #include <bits/stdc++.h>
- #define pb push_back
- #define pf push_front
- #define all(a) (a).begin(), (a).end()
- #define heap priority_queue
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair<ll, ll> pll;
- const ll inf = numeric_limits<ll>::max() / 2;
- const ld eps = 1e-9;
- typedef tuple <ll, ll, ll> triple;
- ll N;
- vector<ll> as;
- vector<ll> pref, suf;
- vector<ll> center;
- vector<triple> ts;
- bool comp(triple a, triple b) {
- if (get<0>(a) != get<0>(b)) {
- return a < b;
- }
- return get<1>(a) > get<1>(b) && get<2>(a) < get<2>(b);
- }
- pll solve() {
- pref.assign(N + 1, 0);
- suf.assign(N + 2, 0);
- for (ll i = 1; i <= N; i++) {
- pref[i] = pref[i - 1] + (as[i] == i);
- }
- for (ll i = N; i >= 1; i--) {
- suf[i] = suf[i + 1] + (as[i] == i);
- }
- for (ll i = 1; i <= N; i++) {
- ll p = as[i] + i;
- ts.pb({ p, min(as[i], i), max(as[i], i) });
- }
- ll ans = 0;
- ll ansi = -1, ansj = -1;
- sort(all(ts), comp);
- center.assign(2 * N + 2, 0);
- for (triple t : ts) {
- ll c, l, r;
- tie(c, l, r) = t;
- ll cnt = 1 + l != r;
- center[c] += cnt;
- ll a = center[c] + pref[l-1] + suf[r+1];
- if (a > ans) {
- ans = a;
- ansi = l, ansj = r;
- }
- }
- return { ansi, ansj };
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- cin >> N;
- as.resize(N + 1);
- for (ll i = 1; i <= N; i++) {
- cin >> as[i];
- }
- pll p = solve();
- cout << as[p.first] << " " << as[p.second] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement