CF1900F Local Deletions

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 \le l \le r \le 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).

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 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 \le a_i \le n $ ) — the elements of permutation $ a $ . The $ i $ -th of the next $ q $ lines contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the description of $ i $ -th query.

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

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.