Longest Magic Subinterval

A magic sequence is defined as a sequence in which every element is between the first and the last element (inclusive) when considering their order. In other words, for a contiguous subarray S with first element x and last element y, if we let m = min(x, y) and M = max(x, y), then the subarray is magic if every element z in S satisfies

[ m \le z \le M ]

You are given an array a of N integers and Q queries. Each query is represented by two integers L and R which specify a segment of the array (using 1-indexing). Your task is to find the length of the longest contiguous subarray (subinterval) within indices [L, R] that is magic.

Note: A subarray of length 1 is always considered magic.

inputFormat

The first line contains two integers N and Q.

The second line contains N integers representing the array a.

Each of the next Q lines contains two integers L and R (1-indexed) representing a query.

outputFormat

For each query, output a single integer on a separate line representing the length of the longest magic subinterval within indices [L, R].

sample

5 3
2 3 1 4 2
1 5
2 4
3 3

2
2
1