Joker and Batman

All submissions for this problem are available.
As you all know about the ruthless fight between Joker and Batman , Joker is one of the person who wants the city to burn in fire in exchange of nothing , not even money . This time Joker has kept people of Gotham as hostages and Batman has to turn up for his duty.Now , Joker wants to check Batman on his concepts of trees, so he provides him a complete Binary tree and ask him several queries . A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Each node of complete Binary tree has a color associated with it .
In each query , Batman is provided with two parameters , U(node number) & K(distinct colors).
For each query consider the subtree rooted at given node U ,determine what is the minimum level at which number of distinct color nodes is greater than or equal to K , otherwise Joker will start killing the people.
For each query ,you have to determine the minimum level (let's say) y and hence output the difference level[y]  level[x] where x is the level of the given node.
For more clarification , see the sample input.
Since Batman is weak at trees , so he has come up to you for rescuing Gotham. Help him .
Note : Large I/O files , please use scanf/printf instead of cin cout .
Input
The first line of input contains number of test cases T.
The first line of each test case contains an integer N the number of nodes of complete Binary tree.
The second line of each test case contains N integers representing array C[i], where C[i] is the color of i^{th} node.
The third line of each test case contains an integer Q the number of queries .
Then Q lines will follow each containing two integers U(node number) and K(distinct colors)
Output
For each query output the desired answer, and if no part of subtree of given node satisfies the given query , output "1" without quotes .
Contraints
 1 ≤ T ≤ 10
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ C[i] ≤ 10 (1 ≤ i ≤ N)
 1 ≤ U ≤ N
 1 ≤ K ≤ 10
Example
Input:
1
15
1 2 1 3 1 4 3 3 5 5 6 7 7 8 9
5
1 9
2 5
8 1
3 4
2 10
Output:
3
2
0
2
1
Explanation
For 2nd query : 2 5
Nodes which are under subtree of 2 and upto level[2] : {2} , distinct color nodes = 1
Nodes which are under subtree of 2 and upto level[2]+1 : {2,4,5} , distinct color nodes = 3
Nodes which are under subtree of 2 and upto level[2]+2 : {2,4,5,8,9,10,11} , distinct color nodes = 5
So answer = 2
For 5th query : 2 10
There is no part of subtree under the node 2 which has number of distinct color nodes >= 10 so , answer = 1
Author:  screw_1011 
Editorial  https://discuss.codechef.com/problems/INSQ16C 
Tags  insomnia, mnnit, screw_1011 
Date Added:  31082016 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions