use proconio::{fastout, input};

#[allow(unused)]
mod mylib {
    pub struct SegmentTree<S: Monoid> {
        container: Vec<Vec<S::T>>,
    }

    pub trait Monoid {
        type T: Clone;
        const DEFAULT: Self::T;
        fn op(a: &Self::T, b: &Self::T) -> Self::T;
    }

    impl<S: Monoid> SegmentTree<S> {
        pub fn update(&mut self, index: usize, value: S::T) {
            self.container[0][index] = value;
            for layer in 1..self.container.len() {
                self.container[layer][index >> layer] = S::op(
                    &self.container[layer - 1][(index >> layer) << 1],
                    &self.container[layer - 1][((index >> layer) << 1) | 1],
                );
            }
        }

        pub fn range_pick_up(&self, mut l: usize, mut r: usize) -> S::T {
            let mut ans_l = S::DEFAULT;
            let mut ans_r = S::DEFAULT;
            for layer in 0..self.container.len() {
                if l >= r {
                    break;
                }
                if ((l >> layer) & 1) == 1 {
                    ans_l = S::op(&ans_l, &self.container[layer][l >> layer]);
                    l += 1 << layer;
                }
                if ((r >> layer) & 1) == 1 {
                    ans_r = S::op(&self.container[layer][(r >> layer) - 1], &ans_r);
                    r -= 1 << layer;
                }
            }

            S::op(&ans_l, &ans_r)
        }
    }

    impl<S: Monoid> From<Vec<S::T>> for SegmentTree<S> {
        fn from(mut value: Vec<S::T>) -> Self {
            let mut st = Self {
                container: Vec::<Vec<S::T>>::new(),
            };
            if value.is_empty() {
                return st;
            }

            let mut len: usize = 1;
            while len < value.len() {
                len *= 2;
            }
            value.extend(vec![S::DEFAULT; len - value.len()]);
            st.container.push(value);

            let len = len;
            let mut layer: usize = 1;
            while (len >> layer) > 0 {
                st.container.push(vec![S::DEFAULT; len]);
                for i in 0..(len >> layer) {
                    st.container[layer][i] = S::op(
                        &st.container[layer - 1][i << 1],
                        &st.container[layer - 1][(i << 1) | 1],
                    );
                }
                layer += 1;
            }
            st
        }
    }

    impl<S: Monoid> std::ops::Index<usize> for SegmentTree<S> {
        type Output = S::T;
        fn index(&self, index: usize) -> &Self::Output {
            &self.container[0][index]
        }
    }

    pub struct MaxSegmentTree<S: Monoid>
    where
        S::T: Clone + PartialOrd,
    {
        st: SegmentTree<S>,
    }

    impl<S: Monoid> MaxSegmentTree<S>
    where
        S::T: PartialOrd,
    {
        pub fn update(&mut self, index: usize, value: S::T) {
            self.st.update(index, value)
        }

        pub fn range_pick_up(&self, l: usize, r: usize) -> S::T {
            self.st.range_pick_up(l, r)
        }

        pub fn leftest_above(&self, border: S::T, mut l: usize, mut r: usize) -> Option<usize> {
            if l >= r || self.st.container.is_empty() {
                return None;
            }

            let mut layer = 0;
            let mut candidate_layer = usize::MAX;
            let mut candidate_index = usize::MAX;
            while layer < self.st.container.len() {
                if (l & 1) == 1 {
                    if self.st.container[layer][l] >= border {
                        candidate_layer = layer;
                        candidate_index = l;
                        break;
                    }
                    l += 1;
                }
                if (r & 1) == 1 {
                    if self.st.container[layer][r - 1] >= border {
                        candidate_layer = layer;
                        candidate_index = r - 1;
                    }
                    // r -= 1;
                }
                layer += 1;
                l >>= 1;
                r >>= 1;
            }
            if candidate_layer == usize::MAX {
                return None;
            }

            while candidate_layer > 0 {
                if self.st.container[candidate_layer - 1][candidate_index << 1] >= border {
                    candidate_index <<= 1;
                } else {
                    candidate_index = (candidate_index << 1) | 1;
                }
                candidate_layer -= 1;
            }
            Some(candidate_index)
        }

        pub fn rightest_above(&self, border: S::T, mut l: usize, mut r: usize) -> Option<usize> {
            if l >= r || self.st.container.is_empty() {
                return None;
            }

            let mut layer = 0;
            let mut candidate_layer = usize::MAX;
            let mut candidate_index = usize::MAX;
            while layer < self.st.container.len() {
                if (r & 1) == 1 {
                    if self.st.container[layer][r - 1] >= border {
                        candidate_layer = layer;
                        candidate_index = r - 1;
                        break;
                    }
                    // r -= 1;
                }
                if (l & 1) == 1 {
                    if self.st.container[layer][l] >= border {
                        candidate_layer = layer;
                        candidate_index = l;
                    }
                    l += 1;
                }
                layer += 1;
                l >>= 1;
                r >>= 1;
            }
            if candidate_layer == usize::MAX {
                return None;
            }

            while candidate_layer > 0 {
                if self.st.container[candidate_layer - 1][(candidate_index << 1) | 1] >= border {
                    candidate_index = (candidate_index << 1) | 1;
                } else {
                    candidate_index <<= 1;
                }
                candidate_layer -= 1;
            }
            Some(candidate_index)
        }
    }

    impl<S: Monoid> From<Vec<S::T>> for MaxSegmentTree<S>
    where
        S::T: PartialOrd,
    {
        fn from(value: Vec<S::T>) -> Self {
            Self {
                st: SegmentTree::<S>::from(value),
            }
        }
    }

    impl<S: Monoid> std::ops::Index<usize> for MaxSegmentTree<S>
    where
        S::T: PartialOrd,
    {
        type Output = S::T;
        fn index(&self, index: usize) -> &Self::Output {
            &self.st[index]
        }
    }
}

struct S {}

impl mylib::Monoid for S {
    type T = u32;
    const DEFAULT: Self::T = u32::MIN;
    fn op(a: &Self::T, b: &Self::T) -> Self::T {
        *a.max(&b)
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        a: [u32; n],
        queries: [(u8, u32); q],
    }

    println!("{}", output(solve(n, q, a, queries)));
}

fn solve(n: usize, q: usize, a: Vec<u32>, queries: Vec<(u8, u32)>) -> Vec<i32> {
    let mut niwaka = mylib::MaxSegmentTree::<S>::from(a);
    let mut ans = Vec::with_capacity(q);
    for (c, x) in queries {
        match c {
            1 => match niwaka.leftest_above(x + 1, 0, n) {
                Some(pos) => {
                    niwaka.update(pos, 0);
                    ans.push((pos + 1) as i32);
                }
                None => ans.push(-1),
            },
            2 => match niwaka.rightest_above(x + 1, 0, n) {
                Some(pos) => {
                    niwaka.update(pos, 0);
                    ans.push((pos + 1) as i32);
                }
                None => ans.push(-1),
            },
            _ => (),
        }
    }
    ans
}

fn output(ans: Vec<i32>) -> String {
    ans.into_iter()
        .map(|x| x.to_string())
        .collect::<Vec<_>>()
        .join("\n")
}