#include "bits/stdc++.h"

using namespace std;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
      for (T &elem: a) is >> elem;
      return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
      for (T elem: a) os << elem << ' ';
      return (os << '\n');
}

#define int long long

struct Node {
      int val, id;

      Node(int val = 1e9, int id = -1) : val(val), id(id) {}

      friend Node operator+(Node x, Node y) {
            if (x.val <= y.val) return x;
            return y;
      }
};

struct Segtree {
      int size;
      vector<Node> tree;

      Segtree(int n) : size(1) {
            while (size < n) size *= 2;
            tree.resize(size * 2);
      }

      Segtree(const vector<int> &a) : Segtree(a.size()) {
            for (int i = 0; i < a.size(); ++i) tree[i + size] = {a[i], i};
            for (int i = size - 1; i > 0; --i) tree[i] = tree[i * 2] + tree[i * 2 + 1];
      }

      void set(int i, int v) {
            tree[i += size].val = v;
            for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1];
      }

      Node get(int l, int r) {
            l += size, r += size - 1;
            Node resl, resr;
            while (l <= r) {
                  if (l & 1) resl = resl + tree[l++];
                  if (r & 1 ^ 1) resr = tree[r--] + resr;
                  l /= 2, r /= 2;
            }
            return resl + resr;
      }
};


signed main() {
#ifdef LOCAL
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#else
      cin.tie(nullptr);
      ios_base::sync_with_stdio(false);
#endif
      int n, q;
      cin >> n >> q;

      vector<int> a(n);
      cin >> a;
      for (int i = 0; i < n; ++i) a[i]--;

      vector<int> prev(n);

      vector<int> res(n);
      auto calc = [&](){
            vector<vector<int>> ids(n);
            for (int i = 0; i < n; ++i) {
                  ids[a[i]].push_back(i);
            }

            for (int i = 0; i < n; ++i) std::reverse(ids[i].begin(), ids[i].end());
            vector<int> kak(n, 1e9);
            Segtree st(kak);
            for (int i = 0; i < n; ++i) {
                  if (!ids[i].empty())
                        st.set(i, ids[i].back());
            }
            int last = -1;
            int lastid = -1;
            for (int i = 0; i < n; ++i) {
                  Node it;
                  if (last == -1) it = st.get(0, n);
                  else {
                        auto t1 = st.get(0, last);
                        auto t2 = st.get(last + 1, n);
                        it = t1 + t2;
//                        it = st.get(0, last) + st.get(last + 1, n);
                        if (it.val == 1e9) {
                              it = st.get(0, n);
                        }
                  }

                  int id = it.val;
                  int val = it.id;

                  ids[val].pop_back();
                  if (!ids[val].empty()) {
                        st.set(val, ids[val].back());
                  } else {
                        st.set(val, 1e9);
                  }

                  res[id] = i + 1;
                  prev[id] = lastid;
                  last = val;
                  lastid = id;
            }
      };

      calc();
      while (q--) {
            int t;
            cin >> t;
            int x;
            cin >> x;
            x--;
            if (t == 1) {
                  if (a[x + 1] == a[x]) continue;
                  if (res[x] > res[x + 1]) continue;
                  calc();
            } else {
                  cout << res[x] << '\n';
            }
      }
}
