지퍼라인

바샤는 근처 숲의 나무에 지퍼라인을 설치하려고 한다. 그는 라인을 가능한 한 길게 만들고 싶지만, 숲에 있는 모든 나무의 높이를 정확히 기억하지는 못한다. 나무 한 그루를 제외하고는 높이를 올바로 기억한다고 확신한다.

숲에는 왼쪽에서 오른쪽으로 1부터 n까지 번호가 붙은 나무 n그루가 한 줄로 서 있다. 바샤에 따르면 i번째 나무의 높이는 $h_i$이다. 길이가 $k$($1 \le k \le n$)인 지퍼라인은 나무 $k$그루 $i_1, i_2, \ldots, i_k$($i_1 < i_2 < \ldots < i_k$)에 걸쳐 있으며, 이 나무들의 높이는 증가하는 수열, 즉 $h_{i_1} < h_{i_2} < \ldots < h_{i_k}$를 이룬다. 지퍼라인의 길이는 이를 이루는 나무의 개수이다.

페챠도 바샤와 함께 이 숲에 있었고, 바샤의 기록에 실수가 있을지도 모른다는 $q$개의 가정을 가지고 있다. 그의 $i$번째 가정은 두 정수 $a_i$, $b_i$로 주어지며, 페챠의 생각에는 $a_i$번 나무의 실제 높이가 $b_i$이다. 페챠의 가정들은 서로 독립적이다.

각 가정에 대해, 그 가정 아래에서 만들 수 있는 지퍼라인의 최대 길이를 구하라.

첫 줄에 나무의 개수 $n$과 페챠의 가정 개수 $m$($1 \le n, m \le 400\,000$)이 주어진다. 다음 줄에는 바샤가 기억하는 나무의 높이 $h_i$($1 \le h_i \le 10^9$) $n$개가 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $a_i$, $b_i$($1 \le a_i \le n$, $1 \le b_i \le 10^9$)가 주어진다.

페챠의 각 가정에 대해, 그 가정 아래에서 만들 수 있는 지퍼라인의 최대 길이를 한 줄에 하나씩 출력한다.

첫 번째 예제를 보자. 첫 번째 가정은 바샤가 기억하는 높이와 실제로 일치한다. 두 번째 가정에서 나무의 높이는 $(4, 2, 3, 4)$이고, 세 번째 가정에서는 $(1, 2, 3, 3)$, 네 번째 가정에서는 $(1, 2, 3, 5)$이다.