#include <bits/stdc++.h>
using namespace std;
enum { RED, BLACK };
struct node {
  int value;
  int color;
  int size;
  node* parent;
  node* left;
  node* right;
};
node nx[131072];
int nxn = 0;
node* nxf = NULL;
node* nalloc() {
  if (nxf) {
    node* ret = nxf;
    nxf = nxf->parent;
    return ret;
  }
  return &nx[nxn++];
}
void nfree(node* n) {
  n->parent = nxf;
  nxf = n;
}
inline node* grandparent(node* n) {
  if (!n || !n->parent) return NULL;
  return n->parent->parent;
}
inline node* uncle(node* n) {
  node* g = grandparent(n);
  if (!g) return NULL;
  if (n->parent == g->left)
    return g->right;
  else
    return g->left;
}
inline node* sibling(node* n) {
  if (n == n->parent->left)
    return n->parent->right;
  else
    return n->parent->left;
}
void rotate_left(node* n) {
  node* p = n->parent;
  node* m = n->right;
  n->size -= m->size;
  m->size += n->size;
  n->right = m->left;
  if (m->left) m->left->parent = n, n->size += m->left->size;
  m->left = n;
  n->parent = m;
  m->parent = p;
  if (p && p->left == n)
    p->left = m;
  else if (p && p->right == n)
    p->right = m;
}
void rotate_right(node* n) {
  node* p = n->parent;
  node* m = n->left;
  n->size -= m->size;
  m->size += n->size;
  n->left = m->right;
  if (m->right) m->right->parent = n, n->size += m->right->size;
  m->right = n;
  n->parent = m;
  m->parent = p;
  if (p && p->left == n)
    p->left = m;
  else if (p && p->right == n)
    p->right = m;
}
node* insert(node* root, int value) {
  node* cur = root;
  node* n = nalloc();
  n->parent = NULL;
  n->left = NULL;
  n->right = NULL;
  n->value = value;
  n->color = RED;
  n->size = 1;
  while (cur && !n->parent) {
    cur->size++;
    if (value < cur->value) {
      if (cur->left)
        cur = cur->left;
      else {
        cur->left = n;
        n->parent = cur;
      }
    } else {
      if (cur->right)
        cur = cur->right;
      else {
        cur->right = n;
        n->parent = cur;
      }
    }
  }
  while (true) {
    if (!n->parent) {
      n->color = BLACK;
      return n;
    }
    if (n->parent->color == BLACK) return root;
    node* u = uncle(n);
    if (!u || u->color == BLACK) break;
    n->parent->color = BLACK;
    u->color = BLACK;
    n = grandparent(n);
    n->color = RED;
  }
  node* g = grandparent(n);
  if (n == n->parent->right && n->parent == g->left) {
    rotate_left(n->parent);
    n = n->left;
  } else if (n == n->parent->left && n->parent == g->right) {
    rotate_right(n->parent);
    n = n->right;
  }
  n->parent->color = BLACK;
  g->color = RED;
  if (n == n->parent->left)
    rotate_right(g);
  else
    rotate_left(g);
  return (root->parent ? root->parent : root);
}
inline void fix_node(node* n, node* other) {
  if (n->left) n->left->parent = n;
  if (n->right) n->right->parent = n;
  if (n->parent) {
    if (n->parent->left == other)
      n->parent->left = n;
    else
      n->parent->right = n;
  }
}
void fix_remove(node* n) {
  while (true) {
    if (!n->parent) return;
    node* s = sibling(n);
    if (s->color == RED) {
      n->parent->color = RED;
      s->color = BLACK;
      if (n == n->parent->left)
        rotate_left(n->parent);
      else
        rotate_right(n->parent);
      s = sibling(n);
    }
    if (n->parent->color == RED || (s->left && s->left->color == RED) ||
        (s->right && s->right->color == RED))
      break;
    s->color = RED;
    n = n->parent;
  }
  node* s = sibling(n);
  if (n->parent->color == RED && (!s->left || s->left->color == BLACK) &&
      (!s->right || s->right->color == BLACK)) {
    s->color = RED;
    n->parent->color = BLACK;
    return;
  }
  if (n == n->parent->left && (!s->right || s->right->color == BLACK)) {
    s->color = RED;
    s->left->color = BLACK;
    rotate_right(s);
  } else if (n == n->parent->right && (!s->left || s->left->color == BLACK)) {
    s->color = RED;
    s->right->color = BLACK;
    rotate_left(s);
  }
  s = sibling(n);
  s->color = n->parent->color;
  n->parent->color = BLACK;
  if (n == n->parent->left) {
    s->right->color = BLACK;
    rotate_left(n->parent);
  } else {
    s->left->color = BLACK;
    rotate_right(n->parent);
  }
}
node* remove(node* root, int value) {
  node* n = root;
  while (n && n->value != value) {
    if (value < n->value)
      n = n->left;
    else
      n = n->right;
  }
  if (!n) return root;
  for (node* cur = n; cur; cur = cur->parent) cur->size--;
  if (n->left && n->right) {
    node* cur = n->left;
    while (cur->right) cur->size--, cur = cur->right;
    cur->size--;
    n->value = cur->value;
    swap(*cur, *n);
    if (cur == cur->left) {
      cur->left = n;
      n->parent = cur;
      fix_node(n, n);
    } else
      fix_node(n, cur);
    fix_node(cur, n);
    if (root == n) root = cur;
  }
  if (n->left) {
    n->left->parent = n->parent;
    fix_node(n->left, n);
    n->left->color = BLACK;
    if (root == n) root = n->left;
    nfree(n);
    return root;
  }
  if (n->right) {
    n->right->parent = n->parent;
    fix_node(n->right, n);
    n->right->color = BLACK;
    if (root == n) root = n->right;
    nfree(n);
    return root;
  }
  if (n->color == BLACK) {
    fix_remove(n);
    while (root->parent) root = root->parent;
  }
  if (n->parent) {
    if (n->parent->left == n)
      n->parent->left = NULL;
    else
      n->parent->right = NULL;
  }
  if (root == n) root = NULL;
  nfree(n);
  return root;
}
int count_less(node* root, int value) {
  int count = 0;
  while (root) {
    if (value < root->value)
      root = root->left;
    else {
      if (root->left) count += root->left->size;
      if (value == root->value) return count;
      count++;
      root = root->right;
    }
  }
  return count;
}
int num_value[100000];
node* num_list[100000];
map<int, int> num_map;
int num_free = 0;
int n;
int row1[100000];
void num_set(int pos, int value) {
  if (row1[pos] != -1) {
    num_list[row1[pos]] = remove(num_list[row1[pos]], pos);
    if (!num_list[row1[pos]]) {
      num_map.erase(num_value[row1[pos]]);
      num_value[row1[pos]] = num_free;
      num_free = row1[pos];
    }
  }
  if (num_map.find(value) != num_map.end())
    row1[pos] = num_map[value];
  else {
    num_map[value] = row1[pos] = num_free;
    num_free = num_value[num_free];
    num_value[row1[pos]] = value;
  }
  num_list[row1[pos]] = insert(num_list[row1[pos]], pos);
}
const int BUCKET = 300;
int nb;
int buckets[100000][(100000 / BUCKET) + 1];
inline int get1(int pos) { return num_value[row1[pos]]; }
inline int get2(int pos) { return count_less(num_list[row1[pos]], pos); }
int get3(int pos) {
  int val = get2(pos);
  int cur = 0;
  int count = 0;
  for (int i = 0; cur + BUCKET <= pos; i++, cur += BUCKET)
    count += buckets[val][i];
  for (; cur < pos; cur++)
    if (get2(cur) == val) count++;
  return count;
}
void update(int pos, int value) {
  if (num_value[row1[pos]] == value) return;
  node* x = num_list[row1[pos]];
  int prev = count_less(x, pos);
  int orig = prev;
  for (int b = pos / BUCKET; b < nb; b++) {
    int count = count_less(x, b == nb - 1 ? n : (b + 1) * BUCKET);
    if (count > prev) {
      if (prev > orig) buckets[prev - 1][b]++;
      buckets[count - 1][b]--;
    }
    prev = count;
  }
  num_set(pos, value);
  x = num_list[row1[pos]];
  prev = count_less(x, pos);
  orig = prev;
  for (int b = pos / BUCKET; b < nb; b++) {
    int count = count_less(x, b == nb - 1 ? n : (b + 1) * BUCKET);
    if (count > prev) {
      if (prev > orig) buckets[prev - 1][b]--;
      buckets[count - 1][b]++;
    }
    prev = count;
  }
}
int main() {
  memset(buckets, 0, sizeof buckets);
  for (int i = 0; i < 100000; i++)
    num_value[i] = i + 1, row1[i] = -1, num_list[i] = NULL;
  scanf("%d", &n);
  nb = (n + BUCKET - 1) / BUCKET;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    num_set(i, x);
    buckets[get2(i)][i / BUCKET]++;
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int q, x, y;
    scanf("%d %d %d", &q, &x, &y);
    if (q == 1)
      update(y - 1, x);
    else {
      if (x == 1)
        printf("%d\n", get1(y - 1));
      else if ((x & 1) == 0)
        printf("%d\n", get2(y - 1) + 1);
      else
        printf("%d\n", get3(y - 1) + 1);
    }
  }
  return 0;
}
