Cho dãy ~a~ gồm ~n~ phần tử. Đoạn ~[l, r]~ của dãy ~a~ là dãy gồm các phần tử liên tiếp ~a_l, a_{l+1}, \dots, a_r~. Độ xấu của đoạn ~[l, r]~ là số lượng vị trí ~i~ (~l \le i \le r~) sao cho ~a_i \neq i - l + 1~.

Yêu cầu: Hãy chia dãy ~a~ thành các đoạn sao cho mỗi phần tử ~a_i~ thuộc đúng một đoạn và tổng độ xấu của các đoạn là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~) tương ứng là độ dài dãy ~a~.
• Dòng thứ hai chứa ~n~ số nguyên lần lượt là ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n, \forall 1 \le i \le n~) tương ứng với giá trị của các phần tử thuộc dãy ~a~.

Output

• Ghi trên một dòng duy nhất là tổng độ xấu nhỏ nhất.

Sample Input 1

5
2 1 3 2 1

Sample Output 1

2

Gọi khoảng cách giữa hai đỉnh ~u, v~ trên cây là số cạnh ít nhất cần đi qua để đi từ ~u~ đến ~v~. Đường kính của một tập đỉnh là khoảng cách xa nhất giữa hai đỉnh trong tập đó.

Bạn được cho ~Q~ truy vấn, truy vấn thứ ~i~ gồm một số nguyên ~v_i~ tương ứng với việc xoá đỉnh ~v_i~ thuộc tập ~A~, và thêm đỉnh ~v_i~ vào tập ~B~.

Yêu cầu: Hãy đưa ra đường kính của tập đỉnh ~A~ và tập đỉnh ~B~ sau mỗi truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên tương ứng là số đỉnh ~N~ (~1 \le N \le 4 \times 10^5~) của cây đồ thị và số truy vấn ~Q~ (~1 \le Q < N~).
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a, b~ (~1 \le a, b \le N~) tương ứng là hai đỉnh có cạnh nối với nhau trên cây.
• ~Q~ dòng cuối cùng, dòng thứ ~i~ là số nguyên ~v_i~ (~1 \le v_i \le N~) tương ứng với truy vấn thứ ~i~. Dữ liệu đảm bảo các ~v_i~ là phân biệt.

Output

• Ghi kết quả trên ~Q~ dòng, dòng thứ ~i~ chứa hai số nguyên tương ứng là đường kính của tập ~A~ và đường kính của tập ~B~ sau truy vấn thứ ~i~.

Sample Input 1

5 4
1 2
2 4
1 3
3 5
2
1
4
3

Sample Output 1

4 0
4 1
1 2
0 3

Cho hai số nguyên dương ~n, k~ và dãy ~a~ có ~n~ phần tử. Xét một dãy ~b~ có ~n~ phần tử ban đầu đều bằng ~\infty~ hay ~b_i = \infty~ với ~\forall 1 \le i \le n~. Bạn được thực hiện thao tác sau vô số lần:

• Chọn cặp số nguyên ~(x, v)~ thỏa mãn ~1 \le x \le n - k + 1~, sau đó gán ~b_i = \min(b_i, v)~ với ~\forall x \le i \le x + k - 1~.

Sau một số thao tác, dãy ~b~ được gọi là đẹp nếu ~a_i \ge b_i~ với ~\forall 1 \le i \le n~.

Yêu cầu: Tính giá trị lớn nhất của tổng các phần tử dãy ~b~ sau khi dãy ~b~ trở nên đẹp.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ (~1 \le k \le n \le 2000~).
• Dòng thứ hai chứa ~n~ số nguyên lần lượt là ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 100\,000~).

Output

• Ghi ra trên một dòng duy nhất là giá trị lớn nhất của tổng các phần tử dãy ~b~ sau khi dãy ~b~ trở nên đẹp.

Sample Input 1

4 2
6 6 4 2

Sample Output 1

16

Sample Input 2

5 3
3 4 4 3 1

Sample Output 2

9