Problem Statement

Consider an array-reduction routine that works on an array of n integers, called arr , by repeating these steps until the array runs out: Initialize an empty array called result . Select an integer k such that 1 ≤ k ≤ length of the array arr . Append the MEX (Minimum Excluded Value) of the first k elements of arr to the result array. Remove the first k elements from arr . Given an array arr , work out the lexicographically largest result array this routine could ever produce. Definitions: An array x is lexicographically greater than an array y if either: at the first position where they differ, x[i] > y[i]; or |x| > |y| and y is a prefix of x . The MEX of a set of non-negative integers is the smallest non-negative integer not present in the set. For example, MEX({1,2,3}) = 0 and MEX({0,1,2,4,5}) = 3. Example: Given n = 4, arr = [0,1,1,0], here's one way to drive result to its lexicographic maximum: Take k = 2: the MEX of the 1st and 2nd elements of arr is 2. So arr = [1,0]