One day, Baraa was in Saudi Arabia. He went to his favourite store that sells games.
He saw many games there but he chose his favourite type of games LEGO.
When he returned to home, he started to play with the new LEGO game but suddenly he found that some piece is lost.
Baby Baraa started to cry and asked his mother to find it but she couldn't I hope you are sad for Baby Baraa.
So here is your problem, You are given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2,a_3,…,a_n$$$ each $$$a_i$$$ is a piece of LEGO of type $$$a_i$$$. There are $$$n$$$ types of LEGO pieces.
You have to answer $$$q$$$ independent queries, each consisting of two integers $$$l$$$ and $$$r$$$. Consider the subarray $$$a[l:r] = [a_l,a_{l+1},…,a_r]$$$.
The answer to the query is any type of LEGO piece that is not found in this subarray.
Can you help Baby Baraa to find any missing piece to make him stop crying ?.
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1≤n,q≤2⋅10^5)$$$ — the length of the array $$$a$$$ and the number of queries.
The next line contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(1≤a_i≤n)$$$ — the pieces of LEGO.
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 the $$$i$$$-th query.
It is garaunteed that there is an answer for each query.
For each query, output a single integer — the type of any LEGO piece that is not found in the subarray from $$$l_i$$$ to $$$r_i$$$.
5 3 1 2 3 5 4 1 3 2 5 2 2
4 1 1
For the first query the elements in the subarray is $$$[1,2,3]$$$ and the missing types of LEGO pieces are $$$4$$$ and $$$5$$$ so you can output anyone of them.
