I'm not sure if it exists O(n) solution.

Anything better,than O(N^2) solution ?

Are you familiar with Sorted Trees?

Hi AZ01, I've got an O(n log n) algorithm which is very easy in implementation because it doesn't require any trees. It uses the trick with a stack about which you've mentioned. I've just developed it a bit. My idea is to go through the array once and remember previous smaller element with maximum index. Simultaneously, you save queries about previous 2nd element. Then, in the second loop, you just answer these queries. My implementation is below. I'm not sure if it's clear so tell me if you don't catch it.

// Szymon Golebiowski 2019
#include <bits/stdc++.h>
using namespace std;
constexpr pair<int, int> NONE = {-1, -1};

class increasing_stack_t {
  public:
    vector<pair<int, int>> s;

    void updateStack(int value, int index) {
        while (!s.empty() && value <= s.back().first)
            s.pop_back();
        s.push_back({value, index});
    }

    pair<int, int> lastLower(int value) {
        if (s.empty())
            return NONE;
        auto it = lower_bound(s.begin(), s.end(), make_pair(value, 0)) - 1;
        if (it >= s.begin())
            return *it;
        return NONE;
    }
} previous;

int main() {
    pair<int, int> a;
    int n;
    cin >> n;
    vector<int> values(n), results(n, 0);
    vector<vector<pair<int, int>>> queries(n);

    for (int i = 0; i < n; i++) {
        cin >> values[i];
        if (NONE != (a = previous.lastLower(values[i])))
            queries[a.second].push_back({values[i], i});
        previous.updateStack(values[i], i);
    }

    previous.s.clear();
    for (int i = 0; i < n; i++) {
        for (auto &el : queries[i])
            if (NONE != (a = previous.lastLower(el.first)))
                results[el.second] = a.first;
        previous.updateStack(values[i], i);
        cout << results[i] << " ";
    }
    cout << endl;

    return 0;
}

Consider p_i to be the maximum index that p_i < i and a_pi < a_i. This can be done in O(n) using a stack.

Consider S_i to be the set of indices like j that p_j = i. Add all elements of S_i behind i and color them red. So like for array [2, 1, 4, 3, 5], p = [0, 0, 2, 2, 4], the new array becomes like this: [2, 4r, 3r, 1, 4, 5r, 3, 5]. (by 4r I mean a red 4).

Construct p for the new array in O(n). The answer is p of red elements! It's easy to prove that so I'll leave it up to you.

you can use solution to previous, two times.

Could you please define 2nd previous minimum? I don't understand why in your first example, the 2nd previous minimum for 7 is 3 or for 10 or 8 is 1. How can 1 ever be a 2nd minimum if there is only one 1 in the array?

One more way to solve this problem is using square root decomposition:

1. Divide the array into sqrt(n) blocks of size sqrt(n) each.

2. For each block you maintain the minimum element encountered

3. You can skip a block if the minimum is greater the current element

Total time complexity would be O(n*sqrt(n))