Algorithm

B. Divine Array
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1602/B
input
standard input
output
standard output

Black is gifted with a Divine array a� consisting of n� (1≤n≤20001≤�≤2000) integers. Each position in a� has an initial value. After shouting a curse over the array, it becomes angry and starts an unstoppable transformation.

The transformation consists of infinite steps. Array a� changes at the i�-th step in the following way: for every position j�, aj�� becomes equal to the number of occurrences of aj�� in a� before starting this step.

Here is an example to help you understand the process better:

Initial array: 22 11 11 44 33 11 22
After the 11-st step: 22 33 33 11 11 33 22
After the 22-nd step: 22 33 33 22 22 33 22
After the 33-rd step: 44 33 33 44 44 33 44
... ...

In the initial array, we had two 22-s, three 11-s, only one 44 and only one 33, so after the first step, each element became equal to the number of its occurrences in the initial array: all twos changed to 22, all ones changed to 33, four changed to 11 and three changed to 11.

The transformation steps continue forever.

You have to process q� queries: in each query, Black is curious to know the value of ax�� after the k�-th step of transformation.

Input

Each test contains multiple test cases. The first line contains the number of test cases t� (1≤t≤10001≤�≤1000). Description of the test cases follows.

The first line of each test case contains an integer n� (1≤n≤20001≤�≤2000) — the size of the array a�.

The second line of each test case contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤n1≤��≤�) — the initial values of array a�.

The third line of each test case contains a single integer q� (1≤q≤1000001≤�≤100000) — the number of queries.

Next q� lines contain the information about queries — one query per line. The i�-th line contains two integers xi�� and ki�� (1≤xi≤n1≤��≤�; 0≤ki≤1090≤��≤109), meaning that Black is asking for the value of axi��� after the ki��-th step of transformation. ki=0��=0 means that Black is interested in values of the initial array.

It is guaranteed that the sum of n� over all test cases doesn't exceed 20002000 and the sum of q� over all test cases doesn't exceed 100000100000.

Output

For each test case, print q� answers. The i�-th of them should be the value of axi��� after the ki��-th step of transformation. It can be shown that the answer to each query is unique.

Example
input
Copy
2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000
output
Copy
1
2
3
3
1
2
Note

The first test case was described ih the statement. It can be seen that:

  1. k1=0�1=0 (initial array): a3=1�3=1;
  2. k2=1�2=1 (after the 11-st step): a1=2�1=2;
  3. k3=2�3=2 (after the 22-nd step): a2=3�2=3;
  4. k4=1�4=1 (after the 11-st step): a6=3�6=3.

For the second test case,

Initial array: 11 11
After the 11-st step: 22 22
After the 22-nd step: 22 22
... ...

 

It can be seen that:

  1. k1=0�1=0 (initial array): a1=1�1=1;
  2. k2=1000000000�2=1000000000: a2=2�2=2;

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<(n)<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t, n;
  cin>>t;
  while(t--){
    cin>>n;
    int arr[n];

    int max = -1;
    for(int i = 0; i < n; i++){
      cin>>arr[i];
      if(arr[i] > max){
        max = arr[i];
      }

    }
    int brr[max][n];

    for(int i = 0; i < n; i++){
      brr[0][i] = arr[i];
    }

    for(int j = 0; j < max; j++){
      unordered_map<int, int> mp;
      for (int i = 0; i < n; i++){
        mp[brr[j][i]]++;
      }
      for(int i = 0; i < n; i++){
        brr[j+1][i] = mp[brr[j][i]];
      }

    }

    int q, a, b;
    cin>>q;
    while(q-- ){
      cin>>a>>b;
      if(b < max){
        cout<<brr[b][a-1]<<endl;
      }
      else{
        cout<<brr[max][a-1]<<endl;
      }

    }
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000

Output

x
–
+
cmd
1
2
3
3
1
2
Advertisements

Demonstration

Codeforcess Solution 1602-B B. Divine Array ,C++, Java, Js and Python ,1602-B,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+