N = gets.to_i def send_query(x, y) STDOUT.puts("? #{x} #{y}") gets.to_i end losers = Hash.new { |h, k| h[k] = [] } winners = [*1..N] while winners.size >= 2 x, y = winners.shift(2) winner = send_query(x, y) winners << winner if x == winner losers[x] << y else losers[y] << x end end top = winners.first winners = losers[top] while winners.size >= 2 x, y = winners.shift(2) winner = send_query(x, y) winners << winner end STDOUT.puts("! #{winners.first}")