This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include "datastructure/cartesian_tree.hpp"
#include <iostream>
int main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
std::vector<int> p = cartesian_tree(a);
for (int i = 0; i < n; i++) std::cout << p[i] << " \n"[i == n - 1];
}
#line 1 "test/library-checker/cartesian_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#line 2 "datastructure/cartesian_tree.hpp"
#include <numeric>
#include <optional>
#include <stack>
#include <vector>
template <typename T>
std::vector<int> cartesian_tree(std::vector<T> &a) {
int n = int(a.size());
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::stack<int> st;
for (int i = 0; i < n; i++) {
std::optional<int> pre = std::nullopt;
while (!st.empty() && a[i] < a[st.top()]) {
pre = st.top();
st.pop();
}
if (pre) p[pre.value()] = i;
if (!st.empty()) p[i] = st.top();
st.push(i);
}
return p;
}
#line 4 "test/library-checker/cartesian_tree.test.cpp"
#include <iostream>
int main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
std::vector<int> p = cartesian_tree(a);
for (int i = 0; i < n; i++) std::cout << p[i] << " \n"[i == n - 1];
}