#include <iostream>
#include <stack>
using namespace std;
int* stockSpan(int* P, int n) {
stack<int> st;
int* spans = new int[n];
for (int i = 0; i < n; ++i) {
while (!st.empty() && P[i] >= P[st.top()]) {
st.pop();
}
spans[i] = st.empty() ? (i + 1) : (i - st.top());
st.push(i);
}
return spans;
}
int main() {
int prices[] = {100, 80, 60, 70, 60, 75, 85};
int n = sizeof(prices) / sizeof(prices[0]);
int* spans = stockSpan(prices, n);
cout << "Stock prices: ";
for (int i = 0; i < n; ++i) {
cout << prices[i] << " ";
}
cout << endl;
cout << "Stock spans for each day: ";
for (int i = 0; i < n; ++i) {
cout << spans[i] << " ";
}
cout << endl;
delete[] spans;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RhY2s+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQqIHN0b2NrU3BhbihpbnQqIFAsIGludCBuKSB7CiAgICBzdGFjazxpbnQ+IHN0OwogICAgaW50KiBzcGFucyA9IG5ldyBpbnRbbl07CiAgICAKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgd2hpbGUgKCFzdC5lbXB0eSgpICYmIFBbaV0gPj0gUFtzdC50b3AoKV0pIHsKICAgICAgICAgICAgc3QucG9wKCk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHNwYW5zW2ldID0gc3QuZW1wdHkoKSA/IChpICsgMSkgOiAoaSAtIHN0LnRvcCgpKTsKICAgICAgICBzdC5wdXNoKGkpOwogICAgfQogICAgCiAgICByZXR1cm4gc3BhbnM7Cn0KCmludCBtYWluKCkgewogICAgaW50IHByaWNlc1tdID0gezEwMCwgODAsIDYwLCA3MCwgNjAsIDc1LCA4NX07CiAgICBpbnQgbiA9IHNpemVvZihwcmljZXMpIC8gc2l6ZW9mKHByaWNlc1swXSk7CiAgICBpbnQqIHNwYW5zID0gc3RvY2tTcGFuKHByaWNlcywgbik7CgogICAgY291dCA8PCAiU3RvY2sgcHJpY2VzOiAiOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBjb3V0IDw8IHByaWNlc1tpXSA8PCAiICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGw7CiAgICAKICAgIGNvdXQgPDwgIlN0b2NrIHNwYW5zIGZvciBlYWNoIGRheTogIjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgY291dCA8PCBzcGFuc1tpXSA8PCAiICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGw7CgogICAgZGVsZXRlW10gc3BhbnM7IAogICAgcmV0dXJuIDA7Cn0=