Ban đầu, Fran có một mảng rỗng ~a~. Fran thực hiện ~n~ truy vấn, mỗi truy vấn có dạng ~x~ — anh ta thêm ~x~ phần tử vào cuối mảng ~a~. Sau mỗi truy vấn, Fran muốn xác định phần tử nhỏ nhất trong mảng ~a~, và khi đã xác định được, anh ta sẽ loại bỏ phần tử đó khỏi mảng mà không làm thay đổi chỉ số của các phần tử còn lại.

Yêu cầu: Hãy xác định chỉ số của phần tử nhỏ nhất trong mảng sau mỗi truy vấn, bằng cách hỏi so sánh giữa các chỉ số.

Interaction

Đây là một bài toán tương tác. Nhiệm vụ của bạn là viết một chương trình tương tác để xử lý các truy vấn.

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 40~) — số lượng truy vấn.

Sau đó là ~n~ dòng, mỗi dòng chứa một số nguyên ~x_i~ (~1 \le x_i \le 2000~), biểu thị số phần tử được thêm vào mảng trong truy vấn thứ ~i~.

Sau mỗi truy vấn, bạn có thể gửi các câu hỏi dạng:

Với điều kiện ~i \neq j~, và cả hai chỉ số ~i, j~ phải là các chỉ số của phần tử hiện chưa bị loại bỏ. Trình chấm sẽ phản hồi:

• 0 nếu ~a_i < a_j~

• 1 nếu ~a_i > a_j~

Sau khi xác định được phần tử nhỏ nhất hiện tại, bạn phải in ra:

Trong đó ~x~ là chỉ số của phần tử nhỏ nhất hiện tại trong mảng ~a~ (chỉ số này chưa bị loại bỏ trước đó). Phần tử tại chỉ số ~x~ sẽ được loại bỏ ngay lập tức khỏi mảng.

Sau đó truy vấn tiếp theo sẽ bắt đầu. Sau truy vấn cuối cùng, chương trình kết thúc. Tổng số phần tử được thêm vào qua tất cả các truy vấn sẽ không vượt quá ~2000~.

Sample Input 1

3
3
1
0
0
1
1
1
0

Sample Output 1

? 1 2
? 1 3
? 2 3
! 2 1
? 1 4
! 4 1
? 1 5
! 1 1

Scoring

Chương trình của bạn sẽ được chấm điểm dựa trên tổng số câu hỏi bạn đã hỏi. Gọi ~q~ là tổng số câu hỏi, điểm được tính như sau:

• Nếu ~q \le 7000~: được 100 điểm

• Nếu ~7000 < q \le 20000~: được 30 điểm

• Nếu ~20000 < q \le 80000~: được 15 điểm

Notes

Giả sử mảng thực tế mà máy chấm giữ (ẩn với người chơi) là ~a = [3,2,4,1,5]~.

Quá trình tương tác có thể diễn ra như sau: