/** made by amunduzbaev **/

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define tut(x) array<int, x> 
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
void fropen(string s) {  freopen((s+".in").c_str(),"r",stdin);  freopen((s+".out").c_str(),"w",stdout);  }
 
const int N = 3e5+5; 
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

#define MULTI 0
int n, m, k, res, s, ans, a[N];
int tree[4*N];

void upd(int i, int v, int lx = 1, int rx = s, int x = 1){
	if(lx == rx){ tree[x] ^= v; return; }
	int m = (lx + rx)>>1;
	if(i <= m) upd(i, v, lx, m, x<<1);
	else upd(i, v, m+1, rx, x<<1|1);
	tree[x] = tree[x<<1] ^ tree[x<<1|1];
}

int get(int l, int r, int lx = 1, int rx = s, int x = 1){
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return tree[x]; 
	int m = (lx + rx)>>1;
	return get(l, r, m+1, rx, x<<1|1) ^ get(l, r, lx, m, x<<1);
}

void solve(int t_case){
	cin>>n>>m;
	s = 1;
	while(s < n) s<<=1;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		upd(i, x);
	}
	while(m--){
		int t; cin>>t;
		if(t == 1){
			int i, v; cin>>i>>v;
			upd(i, v);
		} else {
			int l, r; cin>>l>>r;
			cout<<get(l, r)<<"\n";
		}
	}
}

signed main(){
	NeedForSpeed
	
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	}
	return 0;
}

#include"bits/stdc++.h"
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(x) x.begin(),x.end()
#define MOD 1000000007
#define INF INT_MAX
#define FLOAT_ANS setprecision(10)

using namespace std;
typedef long long ll;

//最大公約数
template<typename T>
T gcd(T a, T b) {
	if (a % b == 0) {
		return(b);
	}
	else {
		return(gcd(b, a % b));
	}
}

//最小公倍数
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}

//Segment Tree(遅延評価)
template<typename T>
class SegTreeLazy {

	//参照：https://algo-logic.info/segment-tree/
public:
	//変数定義
	ll N;  //長さ
	T e; //単位元
	vector<T>seg; //基本
	vector<T>lazy; //遅延用
	function<T(T, T)> f; //比較用


	SegTreeLazy(ll n, ll e_, function<T(T, T)> f_) {
		//サイズ・単位元・比較用の関数
		e = e_;
		f = f_;

		//サイズnのSegTreeに必要な要素数
		ll x = 1;
		while (n > x) {
			x *= 2;
		}
		N = x;

		seg.resize(2 * N - 1, e);
		lazy.resize(2 * N - 1, e);
	}

	T get(ll i){
		return seg[i+N-1];
	}

	void eval(ll k) {
		//lazyから更新情報を取得、segに反映
		if (lazy[k] == e) return; //更新情報がなければ終了
		if (k < N - 1) { //自身が葉でないのなら子にも伝搬させる(zipを解凍)
			lazy[k * 2 + 1] = lazy[k];
			lazy[k * 2 + 2] = lazy[k];
		}

		//最後に、自身を更新
		seg[k] = lazy[k];
		//もう更新情報に用はないので、初期化
		lazy[k] = e;
	}

	void update(ll a, ll b, T x, ll k, ll l, ll r) {
		// a･b:全体の範囲
		// k･l:現在更新するn層目の範囲
		// x:更新する値
		// k:セグ木の配列における位置

		eval(k); //まずは更新(sudo apt update　と同じ感じ?)
		if (a <= l && r <= b) {// 内部にある(端でない)
			//現在の層についてのみ更新させる
			lazy[k] = x;
			eval(k);
		}
		else if (a < r && l < b) {// 一部区間がかぶる
			update(a, b, x, k * 2 + 1, l, (l + r) / 2); //右の子に伝搬
			update(a, b, x, k * 2 + 2, (l + r) / 2, r); //左の子に伝搬
			seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
		}
	}
	void update(ll a, ll b, T x) {
		//(a)-(b-1)の範囲をxに更新
		update(a, b, x, 0, 0, N);
	}
	void update(ll a, T x) {
		//aをxに更新
		update(a, a + 1, x, 0, 0, N);
	}

	T query_sub(ll a, ll b, ll k, ll l, ll r) {
		eval(k);
		if (r <= a || b <= l) {  //完全に外部
			return e;
		}
		else if (a <= l && r <= b) {  //完全に内部
			return seg[k];
		}
		else {
			T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);

			return f(vl, vr); //右の子と左の子の小さい方
		}
	}
	T query(int a, int b) {
		return query_sub(a, b, 0, 0, N);
	}
};


int main(void) {
	ll n;
	cin>>n;
	vector<ll>p(n);
	vector<bool>dp(200010,false);
	ll ans=0;
	rep(i,n){
		cin>>p[i];
		dp[p[i]]=true;
		while(dp[ans]){
			++ans;
		}
		cout<<ans<<endl;
	}
}


/*

*/
