Tất niên

Trong tiệc tất niên cuối năm, gia đình Alice chuẩn bị một bàn tiệc lớn để chào đón mọi người. Trên bàn có $N$ đĩa thức ăn được bày biện đẹp mắt thành một hàng, được đánh số từ $1$ tới $N$ từ trái sang phải. Đĩa thứ $i$ $(1\le i\le N)$ có độ hấp dẫn là một số nguyên dương $A_i$.

Với một đoạn gồm $M$ đĩa ở vị trí liên tiếp của bàn tiệc có độ hấp dẫn tương ứng là dãy $(B_1,B_2,\dots ,B_M)$, Alice định nghĩa độ đa dạng của dãy đó là số lượng dãy khác nhau có thể nhận được bằng cách thực hiện không quá một phép đảo ngược trên dãy. Một phép đảo ngược là việc chọn một cặp chỉ số $(L,R)$ với $1\le L<R\le M$ và thực hiện đảo ngược dãy $(B_L,B_{L+1},\dots ,B_{R-1},B_R)$ thành dãy $(B_R,B_{R-1},\dots ,B_{L+1},B_L)$, các phần tử còn lại giữ nguyên. Hai dãy $(X_1,X_2,\dots ,X_M)$ và $(Y_1,Y_2,\dots ,Y_M)$ được xem là khác nhau nếu tồn tại chỉ số $i$ $(1\le i\le M)$ sao cho $X_i\ne Y_i$. Ví dụ, dãy $(3,1,3)$ có độ đa dạng bằng $3$ vì có thể tạo được $3$ dãy khác nhau với không quá một phép đảo ngược: $(3,1,3)$, $(1,3,3)$, $(3,3,1)$.

Trong buổi tiệc, có $Q$ vị khách lần lượt tới tham dự. Vị khách thứ $j$ $(1\le j\le Q)$ đến và lấy chiếc đĩa thứ $p_j$ để dùng bữa. Sau khi một chiếc đĩa được lấy ra, những chiếc còn lại giữ nguyên vị trí ban đầu và tạo thành các đoạn con ngăn cách bởi các vị trí trống do các đĩa đã được lấy đi. Alice tính độ đa dạng của mỗi đoạn con và muốn biết độ đa dạng lớn nhất trong số chúng.

Yêu cầu: Sau khi mỗi vị khách nhấc một chiếc đĩa đi, hãy tính độ đa dạng lớn nhất trong các đoạn con còn lại.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $Q$ $(1\le Q<N\le 2\times {10}^5)$.
• Dòng thứ hai chứa $N$ số nguyên dương $A_1,A_2,\dots ,A_N$ $(1\le A_i\le {10}^9$ với mọi $i=1,2,\dots ,N)$.
• Dòng thứ $j$ trong số $Q$ dòng tiếp theo chứa một số nguyên dương $p_j$ $(1\le p_j\le N)$. Dữ liệu đảm bảo các giá trị $p_j$ là khác nhau.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng một số nguyên duy nhất là kết quả tìm được sau khi vị khách tương ứng nhấc một chiếc đĩa đi.

Ràng buộc

• $1\le Q<N\le 2\times {10}^5$.
• $1\le A_i\le {10}^9$.
• $1\le p_j\le N$, các $p_j$ đôi một khác nhau.

Subtasks

• Subtask 1 ($30\%$ số điểm): $Q=1$, $N\le 200$.
• Subtask 2 ($30\%$ số điểm): $Q=1$, $N\le 2000$.
• Subtask 3 ($20\%$ số điểm): $Q=1$.
• Subtask 4 ($20\%$ số điểm): Không có ràng buộc nào thêm.

Ví dụ