\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng cặp \((i, j)\) mà \(1 \leq i < j \leq n\) và thỏa \(a_i < a_j\) thì ta sẽ cập nhật kết quả \(res = max\{res, j - i\}\)

• Nếu \(res = 0\) thì ta xuất \(-1\) ngược lại xuất \(res\)

\(\color{orange}{\text{Hint 2 <Dynamic-programming>::<Partial-sum><Suffix-array>}}\)

• Gọi \(mark[]\) là mảng mà vị trí nhỏ nhất của \(x\) trong mảng là \(mark[x]\) và các giá trị không có trong mảng \(a[]\) sẽ nhận giá trị vô nghĩa

• Sau khi đánh dấu các phần tử trong mảng \(a[i] -> mark[a[i]] = min(i)\), ta sẽ dùng kĩ thuật mảng tổng dồn

Ta cần tính \(res = max\{mark[x] - i\} \forall i \in [1\dots n], x \in [a[i]\dots alphabet]\)

Nên ta sẽ tính \(mark[x] = max\{mark[y]\} \forall y \in [x\dots alphabet]\)

Mà một khi có \(mark[x]\), ta tính \(mark[x - 1] = max\{mark[y]\} \forall y \in [x - 1 \dots alphabet] = max\{mark[x - 1], mark[x]\}\) trong \(O(1)\)

\(\color{green}{\text{Preference AC Code }}\): Dynamic-programming(partial-sum, suffix array)

\(^{^{\color{purple}{\text{Complexity : }} O(n + alphabet)\ \color{purple}{\text{time}}\ ||\ O(n + alphabet)\ \color{purple}{\text{memory}}}}\)

const int alphabet = 1e6;
vector<int> mark(alphabet + 1, 0);
int main()
{
    int n = readInt();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        if (mark[a[i]] == 0) mark[a[i]] = i;
    }

    for (int x = alphabet; x >= 1; --x)
        maximize(mark[x - 1], mark[x]);

    int res = 0;
    for (int i = 1; i <= n; ++i)
        maximize(res, mark[a[i]] - i);

    cout << (res > 0 ? res : -1);
    return 0;
}