Processing math: 100%

Задача 6N. Доска объявлений

Автор:Бадерик П.М.   Ограничение времени:1 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

Farpost — самый популярный классифайд Дальнего Востока, где ежедневно публикуются миллионы объявлений.

Быть в топе на Фарпосте — задача со звёздочкой. Один из факторов, который на это влияет — рейтинг продавца (по оценкам покупателей).

Представим, что вы берёте проект на практике в Фарпосте и хотите помочь продавцам скорректировать их поведение на сайте для достижения высокого рейтинга.

Вам нужно проанализировать рейтинг продавца за последние N дней.

Конечно самое интересное в рейтинге — это что такого может сделать продавец, чтобы изменить тренд своего рейтинга (убывающий тренд превратить в возрастающий и наоборот). Для начала найдите, когда происходит правильное изменение тренда.

Кажется не очень сложным, да?)

Но из-за защиты персональных данных пользователей (в том числе и продавцов) вы не можете напрямую получить рейтинг продавца. Такие данные есть только у наших сотрудников.

Зато у вас есть возможность отправить небольшое количество запросов в систему.

Запросы могут быть только 2 видов:

  1. «? rating» - где rating это произвольное целое значение рейтинга на ваш выбор. В ответ вы получите целое число, где первые N битов указывают было ли у продавца в i день рейтинга не меньше, чем rating.
  2. «! k i1 i2 ... ik» - отправить ответ, где k - целое число, количество правильных изменений тренда. А i1, ..., ik - номера дней, в которых произошёл правильный разворот тренда.

Чтобы вас не забанили как бота, вы можете отправить не более 90 запросов.

Формат входных данных

В первой строке входных данных идет целое число N.

Формат выходных данных

В запросе с ответом, позиции экстремумов должны идти по возрастания. Так же обращаю внимание, что номера дней: 0ij<N.

Каждый вопрос и вывод ответа должны заканчиваться символом перевода строки, а также необходимо выполнять сброс буфера flush()

Примечание

i позиция называется правильным разворотом, если hi1>hi<hi+1 или hi1<hi>hi+1.

Напоминаем, что биты нумеруются справа налево.

Ограничения

1n31

1017hi1017

|hihi1|1, где hi - целое число, значение в i день на графике.

Описание 1 примера:

ЗапросОтветБиты
? 971271111111
? 99110001011
? 10100000000

Первый запрос: во все дни рейтинг больше или равен 97.

Второй запрос: только в первый, второй и четвёртый дни рейтинг больше или равен 99.

Третий запрос: во все дни рейтинг меньше чем 101.

Примеры тестов

Стандартный вход Стандартный выход
1
7
127
11
0
? 97
? 99
? 101
! 2 2 3
2
15
32760
0
32765
2016
? 0
? 4
? -1
? 2
! 4 5 6 7 13

0.072s 0.009s 15