Find the Common Difference of an Arithmetic Sequence

You are given a shuffled arithmetic sequence \(A\) of length \(n\). Although the sequence is provided in random order, it is guaranteed that the original sequence forms an arithmetic progression with a common difference \(d\). Your task is to determine the common difference \(d\) of the progression.

The interactor allows you to make two types of queries:

• Type 1: Query the relative order of two elements. Given indices \(x\) and \(y\) (referring to positions in the original unsorted order), the interactor returns \(1\) if the element at index \(x\) is greater than the element at index \(y\) in the sorted arithmetic progression (comparing the true values, not modulo), and \(0\) otherwise. The query format is: > x y.
• Type 2: Query the value (modulo \(p = 10^9+7\)) of the element at a given index \(x\) from the original sequence. The query format is: ? x. Note that you can use this query type at most \(q\) times.

You are allowed a total of at most \(2n\) queries. After your queries, you must immediately output your answer in the format: ! d, then flush the output buffer.

Important: Although the problem is naturally interactive, for the purpose of this task the input will be provided non-interactively. In the offline simulation, the first line contains two integers \(n\) and \(q\). The next line contains \(n\) space-separated integers representing the shuffled arithmetic sequence. Since the sequence is an arithmetic progression, once sorted the minimum and maximum elements define the progression, and the common difference can be computed as:

[ d = \frac{\max(A) - \min(A)}{n-1} ]

If \(n = 1\), output \(0\) as the common difference.

inputFormat

The first line of input contains two integers \(n\) and \(q\) where \(n\) is the length of the arithmetic sequence and \(q\) is the maximum number of type 2 queries allowed (note that for this offline simulation, \(q\) is not used in your computation).

The second line contains \(n\) space-separated integers representing the shuffled arithmetic sequence.

outputFormat

Output a single integer \(d\), the common difference of the arithmetic progression. If \(n = 1\), output \(0\).

sample

1 1
5

0