Monotonic Transformation via XOR Operations

You are given a sequence \(A = [A_1, A_2, \ldots, A_N]\) of length \(N\). You are allowed to perform the following operation:

Choose an index \(i\) and update \(A_i\) to either \(A_i \oplus A_{i+1}\) or \(A_i \oplus A_{i-1}\). (Here, \(\oplus\) denotes the bitwise XOR operation.)

Your task is to determine the minimum number of operations needed to transform the sequence into a monotonic sequence as defined below:

• If \(S = 1\): the sequence must be strictly increasing (i.e. \(A_1 < A_2 < \cdots < A_N\)).
• If \(S = 2\): the sequence must be non-decreasing (i.e. \(A_1 \le A_2 \le \cdots \le A_N\)).

If it is impossible to achieve the desired condition, output -1.

Note: The input sequence length \(N\) is small (for example, \(N \le 10\)), so a breadth-first search (BFS) over the state space is acceptable.

inputFormat

The input consists of three lines:

• The first line contains an integer \(S\) (either 1 or 2), which specifies the type of monotonic sequence required.
• The second line contains an integer \(N\), the length of the sequence.
• The third line contains \(N\) space-separated integers \(A_1, A_2, \ldots, A_N\) representing the sequence.

outputFormat

Output a single integer: the minimum number of operations required to transform the given sequence into the desired monotonic sequence. If it is impossible, output -1.

sample

1
3
1 2 3

0