Army of Me

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN20/hindi/ARMYOFME.pdf), [Bengali](http://www.codechef.com/download/translated/JAN20/bengali/ARMYOFME.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN20/mandarin/ARMYOFME.pdf), [Russian](http://www.codechef.com/download/translated/JAN20/russian/ARMYOFME.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN20/vietnamese/ARMYOFME.pdf) as well. Dr.D has recently been thinking about the phrase "Life is short". He decided to start doing all sorts of exotic stuff he has always wanted to do. But since life is short, he does not have the time to do it all by himself, so he made the Cloninator and used it to create $N$ clones of himself (numbered $1$ through $N$) to help him do all the stuff on his hopetodolist. Dr.D has already lined up the clones; for each $i$ ($1 \le i \le N$), the $i$th clone in the line is the $P_i$th clone created by Cloninator. There are $Q$ items on Dr.D's hopetodolist, so you should process $Q$ queries. For each query, Dr.D wants to choose some parameters $L$ and $R$ such that $1 \le L \le R \le N$ and send the clones $P_L, P_{L+1}, \ldots, P_R$ to do an exotic activity. Dr.D waits until these clones finish and come back before proceeding with the next item on his list (the next query), so a clone may be picked multiple times in different queries. The strength of a group of clones is the maximum number of clones in that group such that their positions in the line are consecutive and they can be reordered in such a way that their ids $P_i$ also become consecutive (they were created consecutively by the Cloninator). Dr.D is wondering if the groups he selects are strong enough for their tasks. For each query, calculate the strength of the group of clones that Dr.D sends to do an exotic activity. ### Input  The first line of the input contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $P_1, P_2, \ldots, P_N$.  The next $Q$ lines describe queries. Each of these lines contains two spaceseparated integers $X$ and $Y$; the values of $L$ and $R$ for this query can be calculated as follows:  Let $last$ be the answer to the previous query, or $0$ if this is the first query.  Calculate $L = ((X + last  1)\,\%\, N) + 1$.  Calculate $R = ((Y + last  1)\,\%\, N) + 1$.  If $L \gt R$, swap $L$ and $R$. ### Output For each query, print a single line containing one integer ― the strength of the given group. ### Constraints  $1 \le N, Q \le 5 \cdot 10^5$  $P_1, P_2, \ldots, P_N$ form a permutation of $1, 2, \ldots, N$  $1 \le X, Y \le N$ ### Subtasks **Subtask #1 (21 points):** $N, Q \le 5,000$ **Subtask #2 (79 points):** original constraints ### Example Input ``` 7 5 2 5 4 6 3 7 1 2 4 5 2 1 7 7 6 3 2 ``` ### Example Output ``` 3 5 1 7 2 ```Author:  kmaaszraa 
Tags  kmaaszraa 
Date Added:  8122019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions