# ARC173-C Not Median

2008diff
https://atcoder.jp/contests/arc173/tasks/arc173_c

## 解法

適当に観察していたら以下の事実を見つけた。

> $P_{i} \gt P_{j}$を満たす要素を「赤」、$P_{i} \lt P_{j}$を満たす要素を「青」と呼ぶことにする。
> 解が$k$以上$\rightarrow$ $P$の$i - k + 1$以上$i + k - 1$以下の$P_{i}$以外をこの順に並べた列の隣接する添字であって同じ色のものが存在しない。

帰納法で多分示せている。$P_{1}$とP_{N}$に関してはこの議論は成り立たないが、それは愚直で良い。

## 実装

#include <bits/stdc++.h>


int N;
int P[300030], I[300030];

template <class IT>
void print(IT first, IT last) {
    for (auto it{first} ; it != last ; it = std::next(it)) {
        std::cout << *it << (std::next(it) == last ? '\n' : ' ');
    }
}

void print(std::vector<int> A) {
    print(A.begin(), A.end());
}

std::vector<int> solve() {
    std::vector<int> col(N);
    std::set<int> set;
    for (int i{} ; i + 1 < N ; i++) set.insert(i);
    std::vector<int> ans(N);
    const int INF{(int)1e9};
    for (int j{} ; j < N ; j++) {
        int i = I[j];
        if (i > 0 and i + 1 < N) {
            int val{INF};
            auto up{set.upper_bound(i)};
            if (up != set.end()) val = std::min(val, *up + 2 - i);
            auto dn{set.lower_bound(i)};
            if (dn != set.begin()) {
                dn = std::prev(dn);
                if (*dn < i - 1) {
                    val = std::min(val, i - *dn + 1);
                }
                else if (dn != set.begin()) {
                    val = std::min(val, i - *std::prev(dn) + 1);
                }
            }
            if (i and i + 1 < N and col[i - 1] == col[i + 1]) val = 3;
            ans[i] = val == INF ? -1 : val;
            if (ans[i] % 2 == 0) ans[i]++;
            if (ans[i] > N) ans[i] = -1;
        }
        col[i] = 1;
        if (i) {
            if (set.contains(i - 1)) set.erase(set.find(i - 1));
            else set.insert(i - 1);
        }
        if (i + 1 < N) {
            if (set.contains(i)) set.erase(set.find(i));
            else set.insert(i);
        }
    } 
    {
        ans[0] = -1;
        int dn{}, up{};
        for (int i{1} ; i < N ; i++) {
            if (P[0] > P[i]) dn++;
            if (P[0] < P[i]) up++;
            if (i % 2 == 0 and dn != up) {
                ans[0] = i + 1;
                break;
            }
        }
    }
    {
        ans[N - 1] = -1;
        int dn{}, up{};
        for (int i{1} ; i < N ; i++) {
            if (P[N - 1] > P[N - 1 - i]) dn++;
            if (P[N - 1] < P[N - 1 - i]) up++;
            if (i % 2 == 0 and dn != up) {
                ans[N - 1] = i + 1;
                break;
            }
        }
    }
    return ans;
}

std::vector<int> brute() {
    const int INF{(int)1e9};
    std::vector<int> ans(N, INF);
    for (int l{} ; l < N ; l++) for (int r{l + 1} ; r <= N ; r++) if ((r - l) % 2) {
        std::vector<std::pair<int, int>> B;
        for (int k{l} ; k < r ; k++) B.push_back(std::pair{ P[k], k });
        std::sort(B.begin(), B.end());
        int mididx{B[(r - l) / 2].second};
        for (int k{l} ; k < r ; k++) if (k != mididx) ans[k] = std::min(ans[k], r - l);
    }
    for (auto& a : ans) if (a == INF) a = -1;
    return ans;
}


int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    // std::mt19937 mt{std::random_device{}()};
    // while (true) {
        // N = mt() % 400 + 3;
        std::cin >> N;
        // std::iota(P, P + N, 0);
        // std::shuffle(P, P + N, mt);
        for (int i{} ; i < N ; i++) {
            std::cin >> P[i];
            P[i]--;
            I[P[i]] = i;
        }
        print(solve());
        // auto my{solve()}, ans{brute()};
        // if (my != ans) {
        //     std::cout << N << std::endl;
        //     for (int i{} ; i < N ; i++) std::cout << P[i] << (i + 1 == N ? '\n' : ' ');
        //     print(my);
        //     print(ans);
        //     std::exit(0);
        // }
        // break;
    // }
}

[提出](https://atcoder.jp/contests/arc173/submissions/58301129)

## 感想

- off-by-oneなどの細かい議論を適当にやってしまった。反省。
- 左端と右端で議論が成り立たないことに愚直を書くまで気づけなかった。最近毎回愚直欠かされていて厳しい。