Observe that, if an integer is not found in $a_1, a_2, \dots, a_n$, than it's a valid answer for any query. So, if there is such an integer, output it.

Otherwise, that must mean that every integer in the range $[1, N]$ is present in the array exactly once. This means that any integer outside the given range will be a valid answer.

This can be easily implemented by keeping track of the frequencies of the elements in the range $[1, N]$ and keeping a set of missing elements.

For a query of type $1$, we decrement the count of the previous element and add it to the set if becomes $0$ (which means the element is now missing), while we increment the count of the new element and remove it from the set if it becomes $1$ (which means the element is not missing anymore).

For a query of type $2$, if the set is not empty, we can output any element from the set, otherwise, we pick any element outside the range (e.g., the first element if $l > 1$, the last otherwise).