#include <bits/stdc++.h>   using namespace std;   long long n, v[500005], lastLeft[500005], lastRight[500005], solLeft[500005],       solRight[500005], sol[500005];   int main() {     cin >> n;     for (int i = 1; i <= n; ++i) {       cin >> v[i];     }     for (int i = 1; i <= n; ++i) {       lastLeft[i] = 0;     }     for (int i = n; i >= 1; --i) {       lastRight[i] = n + 1;     }     stack<pair<long long, long long> > st1;     st1.push({1, v[1]});     for (int i = 2; i <= n; ++i) {       while (!st1.empty() && v[i] <= st1.top().second) st1.pop();       if (!st1.empty()) lastLeft[i] = st1.top().first;       st1.push({i, v[i]});     }     stack<pair<long long, long long> > st2;     st2.push({n, v[n]});     for (int i = n - 1; i >= 1; --i) {       while (!st2.empty() && v[i] <= st2.top().second) st2.pop();       if (!st2.empty()) lastRight[i] = st2.top().first;       st2.push({i, v[i]});     }     long long big = 0;     for (int varf = 1; varf <= n; ++varf) {       solLeft[varf] =           solLeft[lastLeft[varf]] + abs(lastLeft[varf] - varf) * v[varf];     }     for (int varf = n; varf >= 1; --varf) {       solRight[varf] =           solRight[lastRight[varf]] + abs(lastRight[varf] - varf) * v[varf];     }     for (int varf = 1; varf <= n; ++varf) {       if (solLeft[varf] + solRight[varf] - v[varf] > big)         big = solLeft[varf] + solRight[varf] - v[varf];     }     for (int varf = 1; varf <= n; ++varf) {       if (solLeft[varf] + solRight[varf] - v[varf] == big) {         sol[varf] = v[varf];         for (int i = varf - 1; i >= 1; --i) {           sol[i] = min(sol[i + 1], v[i]);         }         for (int i = varf + 1; i <= n; ++i) {           sol[i] = min(sol[i - 1], v[i]);         }         for (int i = 1; i <= n; ++i) cout << sol[i] <<    ;         return 0;       }     }     return 0;   }   