write a go solution for Description:
For an array b_1,b_2,ldots,b_m, for some i (1<i<m), element b_i is said to be a local minimum if b_i<b_i-1 and b_i<b_i+1. Element b_1 is said to be a local minimum if b_1<b_2. Element b_m is said to be a local minimum if b_m<b_m-1.

For an array b_1,b_2,ldots,b_m, for some i (1<i<m), element b_i is said to be a local maximum if b_i>b_i-1 and b_i>b_i+1. Element b_1 is said to be a local maximum if b_1>b_2. Element b_m is said to be a local maximum if b_m>b_m-1.

Let x be an array of distinct elements. We define two operations on it:

- 1 — delete all elements from x that are not local minima.
- 2 — delete all elements from x that are not local maxima.

Define f(x) as follows. Repeat operations 1,2,1,2,ldots in that order until you get only one element left in the array. Return that element.

For example, take an array [1,3,2]. We will first do type 1 operation and get [1,2]. Then we will perform type 2 operation and get [2]. Therefore, f([1,3,2])=2.

You are given a permutation^dagger a of size n and q queries. Each query consists of two integers l and r such that 1<=l<=r<=n. The query asks you to compute f([a_l,a_l+1,ldots,a_r]).

^dagger A permutation of length n is an array of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3, but there is 4 in the array).

Input Format:
The first line contains two integers n and q (1<=n,q<=10^5) — the length of the permutation a and the number of queries.

The second line contains n integers a_1,a_2,ldots,a_n (1<=a_i<=n) — the elements of permutation a.

The i-th of the next q lines contains two integers l_i and r_i (1<=l_i<=r_i<=n) — the description of i-th query.

Output Format:
For each query, output a single integer — the answer to that query.

Note:
In the first query of the first example, the only number in the subarray is 1, therefore it is the answer.

In the second query of the first example, our subarray initially looks like [1,4]. After performing type 1 operation we get [1].

In the third query of the first example, our subarray initially looks like [4,3]. After performing type 1 operation we get [3].

In the fourth query of the first example, our subarray initially looks like [1,4,3,6]. After performing type 1 operation we get [1,3]. Then we perform type 2 operation and we get [3].

In the fifth query of the first example, our subarray initially looks like [1,4,3,6,2,7,5]. After performing type 1 operation we get [1,3,2,5]. After performing type 2 operation we get [3,5]. Then we perform type 1 operation and we get [3].

In the first and only query of the second example our subarray initially looks like [1,2,3,4,5,6,7,8,9,10]. Here 1 is the only local minimum, so only it is left after performing type 1 operation.. Output only the code with no comments, explanation, or additional text.