A. Canonical Palindromes
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A palindrome is an array of integers that is equal to the reverse of the same sequence. Emmett finds palindromes too confusing, so he decided to make palindromes more "canonical." A palindrome is a canonical palindrome if the first half of the palindrome is non-decreasing and the second half of the palindrome is non-increasing.

Emmett now wants to determine how he might transform an arbitrary array $$$a$$$ of length $$$k$$$ into a canonical palindrome. To do this, he has decided to perform the following operation:

  1. Choose an integer $$$i$$$ such that $$$1 \leq i \leq k$$$ and let $$$j = k-i+1$$$. Set $$$x = a_i$$$ and $$$y = a_j$$$, then remove $$$a_i$$$ and $$$a_j$$$ from $$$a$$$.
  2. Choose whether or not to swap the values of $$$x$$$ and $$$y$$$.
  3. Partiton $$$a$$$ into three subarrays: $$$p$$$, $$$m$$$, and $$$s$$$.
    • Let $$$p$$$ be some prefix of the array and $$$s$$$ be some suffix of the array, such that the lengths of $$$p$$$ and $$$s$$$ are equal.
    • Let $$$m$$$ be the remaining subarray after removing $$$p$$$ and $$$s$$$.
    • Any of these subarrays are allowed to be empty, as long as $$$p+m+s$$$ is equal to $$$a$$$.
  4. Set $$$a$$$ equal to $$$p + x + m + y + s$$$ where '+' represents the concatenation of two arrays.

All steps of the operation must be performed, and they must be performed in the order stated above. To avoid weird interactions with the middle element, Emmett has decided that the length of the array must always be even.

Emmett wants you to find the minimum number of operations to turn the array into a canonical palindrome, or state if it is impossible to ever do so; however, the data he wrote for this problem got corrupted! Several arrays got merged into a single input file, and instead of fixing the data, he has decided that you must solve this problem for queries on a given array of length $$$n$$$ of the following form:

  • Given two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \lt R \leq n$$$, $$$R-L+1$$$ is even), determine the minimum number of operations to turn $$$a_L$$$, $$$a_{L+1}$$$, ... , $$$a_{R-1}$$$, $$$a_R$$$ into a canonical palindrome.
Input

The first line of input consists of two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n, q \leq 5\cdot 10^5$$$) — the size of the array and the number of queries.

The second line of input consists of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ... , $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of array $$$a$$$.

The following $$$q$$$ lines will consist of two integers corresponding to the query described above.

Output

For each query, output a line with a single integer denoting the minimum number of operations to turn the subarray into a canonical palindrome. If the subarray cannot be turned into a canonical palindrome, output $$$-1$$$.

Example
Input
14 4
2 1 1 2 1 3 1 2 1 5 5 1 2 1
1 4
6 9
7 14
9 12
Output
1
-1
1
0