Lucky invites his friends on his birthday party. Only N friends, numbered from 1 to N came to his house.
They all sit around a circular table around which N chairs are placed. They sit in a such a manner that ith friend will sit in between (i-1)th and (i+1)thth friend.
Nth friend will sit adjacent to 1st friend. After dinner all the adjacent friends of Lucky became friends with each other except 1st friend as he is arrogant. He doesn't make any friends and vice versa.
After six months, Lucky invites all of them to his reception and this time they are standing in a queue in a random order for food.
Now Lucky gives you queries and in each query he will give you the starting index, L of that random order and ending index, R. You will have to tell him, the minimum number of groups of friends in that range.
In a group, each friend has atleast one friend in that group.
Every friend is a friend of himself.
First line of the input contains two space separated integers N and Q.
Second line of the input contains N space separated integers denoting the random order of the friend in the queue.
Next Q lines of the input will contains single space separated pair of integers L and R denoting each query.
For each query ,print a single line containg the minimum number of groups.
Constraints and Subtasks
Subtask 1: 20 points
Subtask 2: 80 points
Input: 4 3 4 2 1 3 1 3 1 4 3 4 Output: 3 2 2
As in first query, 1 has no friend,so it will be in a separate group. 4 and 2 are not friends of each other .So,3 groups will be formed. in 2nd query, 2 and 3 are friends, 3 and 4 are friends. so [2,3,4] will form a group as in this group each has at least one friend. so the answer is 2.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions