Thang máy

Bạn có bao giờ để ý rằng khi ở trong một thang máy chật hẹp, những người ở trong (phía xa hơn so với cửa) nếu muốn dừng tại một tầng, thì khi đó họ phải nhờ những người ở ngoài tránh qua hoặc đi ra khỏi thang máy thì họ mới dừng tại tầng đó được.

Hôm nay bạn gặp một tình huống tương tự, bây giờ bạn đang ở trong một thang máy rất dài đủ cho bất kì số người nào, nhưng lại quá hẹp để hai người có thể đứng cạnh nhau. Thay vào đó, thì những người trong thang máy lại phải xếp một hàng dọc.

Hiện trong thang máy có \(N\) người, theo thứ tự từ gần đến xa cửa thang máy, người thứ \(i\) muốn dừng tại tầng \(a_i\). Khi thang máy dừng ở một tầng, người cần ra ở tầng đó sẽ bước ra, nhưng nếu có người đứng trước họ thì những người đó phải tạm thời bước ra trước rồi mới quay lại. Khi quay lại, họ có thể tự do xếp lại vị trí của mình. Lưu ý chỉ những người đã bước ra trong lượt đó mới có thể sắp xếp vị trí với nhau.

Bạn quan sát tình huống này và tự hỏi: tổng cộng sẽ có bao nhiêu lượt người bước ra khỏi thang máy nếu mọi người luôn trở lại vị trí tối ưu?

Không dừng lại ở đó, bạn còn tò mò nhiều hơn và tự đặt ra \(q\) câu hỏi. Câu hỏi thứ \(i\) là nếu ban đầu không có những người ở vị trí \(x_1, x_2, \cdots x_i\) đứng trong thang máy, thì số lượt ra vào nhỏ nhất là bao nhiêu?

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((0 \leq q \lt n \leq 5 \cdot 10^5)\) --- số người ban đầu và số câu hỏi.

Dòng thứ hai chứa \(n\) số nguyên phân biệt \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq n)\) --- tầng mà người thứ \(i\) muốn đến.

Mỗi dòng trong \(q\) dòng tiếp theo chứa một số nguyên \(x_i\) \((1 \leq x_i \leq n)\). Đảm bảo \(x_i\) phân biệt.

Output

In ra \(q+1\) số trên một dòng:

• Số đầu tiên là số lượt bước ra khỏi thang máy trong trạng thái ban đầu.
• \(q\) số tiếp theo là số lượt nếu giả sử không có những người ở vị trí \(x_1, x_2, \cdots x_i\) đứng trong thang máy.

Example

5 2
3 4 1 2 5
3 2

9 6 4 

7 0
4 5 2 1 6 3 7

13 

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Giới hạn

\hline
1 & 16 & \(n, q \leq 100\)

2 & 19 & \(n, q \leq 1\,000\)

3 & 25 & \(q = 0\)

4 & 40 & Không có ràng buộc khác

\hline
\endtabular