Problem J
Homework Help
Alice was recently given a homework assignment to write a program that would output the number of inversions in any subarray of a given permutation. She happily turned it in and got full marks on her assignment. The next week, their homework assignment was to find the length of the longest increasing subsequences in the same array. Unfortunately, Alice had already thrown away the paper that contained the permutation she needed.
Luckily, this permutation was stored in the program she wrote. Unfortunately, she is now only able to query for the number of inversions in the subarrays of the permutation. As class is close to starting, she asks you for help to solve this problem in a timely manner.
A sequence $a$ is a subsequence of an array $b$ if it is possible to delete some (possibly zero) elements from $b$ to get $a$. A sequence is increasing if every element is strictly greater than all preceding ones, and the LLIS of an array is the length of the longest increasing subsequence.
Interaction
This is an interactive problem.
Interaction starts by reading a single integer $n$ ($1 \le n \le 10^3$), the length of the permutation $p$.
You are then able to make at most $n$ queries of the form ? l r where $1 \le l \le r \le n$. Each query should be on a single line. After each query, read in a single integer, the number of inversions in the subarray $[l, r]$. An inversion is a pair of integers $(x, y)$ where $l \le x < y \le r$ and $p_x > p_y$.
When you have determined the LLIS, output the answer in the form: ! ans on a single line, where ans is the LLIS. After outputting the answer, your program should exit. If you attempt to read a response after outputting an answer, you will receive an arbitrary verdict.
Do not forget to flush the output after each query you output.
The interactor is not adaptive: When the interaction begins, the permutation $p$ is already determined. It is guaranteed that each integer from $1$ to $n$ appears exactly once.
If the interactor receives any invalid or unexpected input, the interactor will output $-1$ and then immediately terminate. Your program should cleanly exit in order to receive a Wrong Answer verdict, otherwise the verdict that it receives may be an arbitrary verdict indicating that your submission is incorrect.
If your program terminates before outputting the answer, your submission will receive an arbitrary verdict indicating that your submission is incorrect.
You are provided with a command-line tool for local testing. The tool has comments at the top to explain its use.
| Read | Sample Interaction 1 | Write |
|---|
3
? 1 3
1
? 1 2
1
! 2
