Cosider a sequence, consisting of
n integers:
a1,
a2,
...,
an. Jeff can perform the following operation on sequence
a:
-
take three integers v, t, k (1≤v,t≤n;0≤k;v+tk≤n), such that av = av+t, av+t = av+2t, ..., av+t(k-1) = av+tk;
-
remove elements av, av+t, ..., av+t·k from the sequence a, the remaining elements should be reindexed a1,a2,...,an-k-1.
-
permute in some order the remaining elements of sequence a.
A beauty of a sequence
a is the minimum number of operations that is needed to delete all elements from sequence
a.
Jeff's written down a sequence of
m integers
b1,
b2,
...,
bm. Now he wants to ask
q questions. Each question can be described with two integers
li,ri. The answer to the question is the beauty of sequence
bli,
bli+1,
...,
bri. You are given the sequence
b and all questions. Help Jeff, answer all his questions.