Lelud

시간 제한1초메모리 제한1024 MB

요약

홀수 크기 부분집합의 선호도 중앙값만 돌려주는 질의로 N개 장난감의 전체 선호 순위를 알아낸다.

난이도: 보통10점 중 7점
유형: 분할 정복, 정렬, 백트래킹
정답자: 아직 제출이 없습니다

문제

Aednik Kazimiri pojal Afanasil on $N$ mänguasja, mida tähistame $1 \ldots N$ . Afanasil on mängu\-asjade osas kindlad eelistused. Täpsemalt on igal mänguasjal $i$ tema eelistuste pingereas positsioon $P\_i$ (kus $1 \le P\_i \le N$ ja $P\_i$ väärtused on paarikaupa erinevad). Seejuures $P\_i = 1$ tähendab, et mänguasi $i$ meeldib talle kõige rohkem, ja $P\_i = N$ , et mänguasi $i$ meeldib talle kõige vähem.

Kazimir teab, et Afanasile meeldib mänguasi $1$ rohkem kui mänguasi $N$ (s.t $P\_1 < P\_N$ ) ja lisaks on ta märganud, et kui Afanasi ette panna $L$ mänguasja (kus $L$ on paaritu arv), siis näitab poiss alati näpuga sellele, mis oleks nende järjestamisel meeldivuse järjekorras täpselt keskmisel kohal.

Kazimir tahab nüüd selle tähelepaneku abil kogu eelistuste pingerea välja selgitada. Aga tal on parajasti aiatöödega kiire ja sellepärast ei saa ta teha liiga palju katseid.

예제1

예제 1

입력

예상 출력


? 5 4 1 2 3 5

? 3 2 4 5

? 3 1 3 4

! 1 5 2 3 4