#include <iostream>
#include <fstream>
#include <iomanip>
#include <random>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <bitset>
//#define int long long
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front

using namespace std;
using ll = long long;
using ld = long double;

void sol() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) swap(a[x], a[x - 1]);
        else {
            int r = -1, c = 0;
            for (int i = 1; i < n; i++) {
                if (a[i] != a[i - 1]) {
                    r = i;
                    break;
                }
            }
            if (r == -1) {
                cout << x << '\n';
                continue;
            }
            vector<bool> vis(n);
            int l = 0;
            for (int i = 0; i < n; i++) {
                int val = 0;
                if (c == 1) {
                    val = r;
                    vis[r++] = 1;
                    if (r < n && a[r] != a[r - 1]) {
                        swap(l, r);
                    } else c = 0;
                } else {
                    val = l;
                    vis[l++] = 1;
                    while (l < n && vis[l]) l++;
                    if (l < n && l == r) {
                        while (r < n && a[r] == a[l]) {
                            r++;
                        }
                        if (r < n && a[l] == a[val]) c = 1;
                    } else if (r < n) c = 1;
                }
                if (val + 1 == x) {
                    cout << i + 1 << '\n';
                    break;
                }
            }
        }
    }
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    sol();
    return 0;
}
