#each.with_indexとeach_with_indexの差をテストしてみる。 #配列aが昇順にソートされた状態を保ったまま要素nを入れる場合に、 #どの位置にインサートすればよいかを返す。 def insert_index(a, n) l = 0 r = a.length return 0 if r == 0 while l < r do m = (l + r) / 2 case n <=> a[m] when 1 then return m + 1 if r - l <= 1 l = m when 0 then return m + 1 when -1 then return m if r - l <= 1 r = m end end end gets a = gets.split.map(&:to_i) max_idxs = Hash.new{} #数が最後に現れるインデックスを格納する。 a.each_with_index do |n, idx| max_idxs[n] = idx end ans = [] open_nums = [] #今までに現れた数。要素は昇順にソートされている。出力に不要となった要素は削除される。 a.each_with_index do |n, idx| open_nums.insert(insert_index(open_nums, n), n) open_nums.pop while open_nums.size > 0 && idx > max_idxs[open_nums[-1]] #末尾の数がもう現れない数の場合、削除する。 ans << open_nums[-1] end puts ans.join(" ")