// All HackerRank test-cases pass, for Max Score of 60
//      Time-Complexity: O(n) | Space-Complexity: O(n)

// NOTE: "debugPrintArr" only given for Diagnostic / Debug purposes.
//       Uncommenting that results in slow-down, hence 1 TC fails with TLE.


public class Solution {

    // Only given for Diagnostic / Debug purposes
    // static void debugPrintArr(int[] arr, String arrName) {
    //     System.err.println("Arr '" + arrName + "' BGN -->");
    //     System.err.print(">");
    //     for (int i = 0 ; i < arr.length ; i++) {
    //         System.err.print(arr[i]);
    //         if (i != (arr.length - 1)) {
    //             System.err.print(" ");
    //         }
    //     }
    //     System.err.print("<"); System.err.println("");
    //     System.err.println("<-- Arr '" + arrName + "' END");
    //     System.err.println("");
    // }

    // Only given for Diagnostic / Debug purposes
    // static void debugPrintArr(long[] arr, String arrName) {
    //     System.err.println("Arr '" + arrName + "' BGN -->");
    //     System.err.print(">");
    //     for (int i = 0 ; i < arr.length ; i++) {
    //         System.err.print(arr[i]);
    //         if (i != (arr.length - 1)) {
    //             System.err.print(" ");
    //         }
    //     }
    //     System.err.print("<"); System.err.println("");
    //     System.err.println("<-- Arr '" + arrName + "' END");
    //     System.err.println("");
    // }

    // Complete the riddle function below.
    static long[] riddle(long[] arr) {

        // complete this function
        int n = arr.length;

        // The Stack stores Indices of "arr". As we iterate through the Array,
        // either forwards or backwards, we keep accumulating indices encountered.
        // But before this, if the Stack isn't empty, and arr[stack.peek()] >= arr[i])
        // Then we Pop from the Stack. This way, we maintain relevant indices in the Stack.
        // So that we can compute the Next Smaller Element in either Direction.
        Stack<Integer> stack = new Stack<>();

        int[] prevSmallerToLeft = new int[n];
        int[] nextSmallerToRight = new int[n];

        // Compute PREVIOUS smaller on LEFT, with help from Stack
        for (int i = 0 ; i < n ; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            prevSmallerToLeft[i] = ( stack.isEmpty() ? -1 : stack.peek() );
            stack.push(i);
        }
        //debugPrintArr(prevSmallerToLeft, "prevSmallerToLeft");

        // Clear Stack
        stack.clear();

        // Compute NEXT smaller on RIGHT, with help from Stack
        for (int i = (n - 1) ; i >= 0 ; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            nextSmallerToRight[i] = ( stack.isEmpty() ? n : stack.peek() );
            stack.push(i);
        }
        //debugPrintArr(nextSmallerToRight, "nextSmallerToRight");

        // ans[len]: max of minimums for window length = len
        long[] ans = new long[n + 1];
        Arrays.fill(ans, 0);

        // Iterating through Left/Right arrays, taking difference (len)
        // And finding the Max of Minimums, b/w "ans[len]" & "arr[i]"
        for (int i = 0 ; i < n ; i++) {
            int len = nextSmallerToRight[i] - prevSmallerToLeft[i] - 1;
            ans[len] = Math.max(ans[len], arr[i]);
        }
        //debugPrintArr(ans, "ans (initial)");

        // Fill remaining sizes
        for (int size = (n - 1) ; size >= 1 ; size--) {
            ans[size] = Math.max(ans[size], ans[size + 1]);
        }
        //debugPrintArr(ans, "ans (final)");

        // Prepare result for sizes 1 through n
        long[] result = new long[n];
        for (int k = 1; k <= n; k++) {
            result[k - 1] = ans[k];
        }
        //debugPrintArr(result, "result");

        return result;

    }
}