Queen of Hearts

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Wonderland is a wonderful world inhabited by N strange creatures, for simplicity all creatures are numbered from 1 to N. Every creature has exactly one best friend (it could be himself too). Note that, the friendship relationship is not bidirectional, meaning that it might be the case person x is best friend of y, but y is not best friend of x. Besides that, there is a very intricate admiration relationship among the creatures. Every creature admires himself and to all the creatures admired by his best friend.
Wonderland is divided in many guilds, each creature belonging to exactly one guild, also each guild contains at least one creature. A guild is defined as the largest set of creatures in which if we take any two creatures i, j, then there exists a creature k such that both i and j admire k. For given best friend relationship for all persons, the guilds formed will be uniquely defined.
The queen of hearts is very angry because someone stole her tarts, so she is going to perform many executions. After the executions some of the creatures will lose his best friend, and will stop admiring all the creatures admired by his best friend, in consequence the number of guilds could change.
Alice have Q queries of the form L, R, and she asks you to determine the number of guilds after the executions if the only survivors are the creatures numbered from L to R.
Input
The first line of the input contains two integers N and Q.
In the next line there are N space separated integers, the ith integer a_{i} represents the best friend of the ith creature.
Then follows Q lines each one with two integers L, R representing one query.
Output
For each query, output the number of guilds after the execution.
Constraints
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ L ≤ R ≤ N
 1 ≤ a_{i} ≤ N
Example
Input: 9 3 2 8 4 3 9 9 8 3 3 1 6 7 9 3 6 Output: 4 2 3
Explanation
Initially there is just one guild.
After the executions of the first query the guilds will be { {1, 2}, {3, 4}, {5},{6} }.
After the executions of the second query the guilds will be { {7, 8}, {9} }.
After the executions of the third query the guilds will be { {3,4}, {5},{6} }.
Author:  alei 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/questions/84223/qeaheaeditorial 
Tags  alei, cook73, datastructure, mediumhard, qeahea, segmenttree 
Date Added:  25072016 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 