eolymp
bolt
Try our new interface for solving problems
Problems

Permutation

Permutation

Time limit 1 second
Memory limit 122 MiB

You are given a permutation of first n positive integers in array. Print the smallest index of array that contains the number in the range from a to b (inclusive).

Input data

First line contains two integers n and q (n, q10^5) separated by a space. Second line contains a permutation of n integers (from 1 to n in any order). Then q lines follow: each line contains two integers a and b (ab10^5) separated by space.

Output data

Print exactly q lines each containing the answer.

Examples

Input example #1
2 2
2 1
1 2
1 1
Output example #1
1
2