题目描述

给你一个长度为 $n$ 的排列 $a$，然后操作 $\lfloor \dfrac{n}{2} \rfloor$ 次。

其中第 $i$ 次操作（$i\in [1,\lfloor \frac{n}{2}]$）会让区间 $[i, n-i+1]$ 的元素顺序翻转。

• 即 $a_i,a_{i+1}, \dots, a_{n-i},a_{n-i+1}$ 变为 $a_{n-i+1},a_{n-i}, \dots ,a_{i+1},a_{i}$。

现在有 $q$ 次询问，每次请你求出第 $x$ 次操作后 $a_y$ 的值。

输入格式

第一行两个正整数 $n,q$，分别表示排列的长度和询问的次数。

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，保证 $1 \leq a_i \leq n$，且两两不同。

接下来 $q$ 行，每行两个正整数 $x, y$，表示询问第 $x$ 次操作后 $a_y$ 的值。

输出格式

输出 $q$ 个正整数，表示每次询问的答案。

7 5
4 3 6 5 7 1 2
1 3
2 1
2 2
2 5
3 2

7 2 3 7 3 

数据范围

对于 $100\%$ 的数据，保证 $1\leq n,q \leq 10^5$。

下发样例

附件