(squeperm.*)

Cho dãy A gồm n phần tử a₁, a₂, ..., a_n là một hoán vị của tập số nguyên dương {1, 2, ..., n}.

Dãy B được tạo như sau: b_i có giá trị là vị trí của phần tử trong dãy A nhỏ hơn a_i và có vị trí gần i nhất. Nếu có 2 giá trị cùng nhỏ hơn a_i và khoảng cách của chúng tới i là bằng nhau thì chọn vị trí của giá trị lớn hơn trong 2 giá trị đó (với i = 1, 2, …, n).

Sau khi có dãy B thì dãy A được biến đổi như sau: mỗi giây, với mỗi i từ 1 tới n, ta thay a_i bằng a_bi . Nếu vị trí i không tồn tại giá trị b_i thì a_i = 0 (với i = 1, 2, …, n; giá trị của dãy B là không thay đổi qua các giây)

Ví dụ: A = [4,2,3,7,8,6,5,1], ta sẽ có B = [2,8,2,3,4,7,8,0] (0 nghĩa là không tồn tại giá trị).

Như vậy lúc đầu: A = [4,2,3,7,8,6,5,1]

• Sau giây thứ 1: A = [2,1,2,3,7,5,1,0]

• Sau giây thứ 2: A = [1,0,1,2,3,1,0,0]

• Sau giây thứ 3: A = [0,0,0,1,2,0,0,0]

• Sau giây thứ 4: A = [0,0,0,0,1,0,0,0]

• Sau giây thứ 5: A = [0,0,0,0,0,0,0,0]

Yêu cầu: Cho q truy vấn, mỗi truy vấn cho hai số nguyên dương x và y. Câu trả lời cho một truy vấn là sau ít nhất bao nhiêu giây thì a_x = y ? Nếu không bao giờ a_x = y thì câu trả lời là -1. Vì số lượng truy vấn là rất lớn nên chỉ cần tính tổng kết quả (câu trả lời) của tất các cả truy vấn (cho biết kết quả này không vượt quá 10¹⁸).

Dữ liệu vào:

• Dòng thứ nhất chứa hai số nguyên dương n và q (n, q ≤ 10⁶);

• Dòng thứ hai chứa n số nguyên dương a₁, a₂, ..., a_n (a_i ≤ n với i = 1, 2, …, n);

(Chú ý: giá trị các phần tử của dãy A là hoán vị của tập số nguyên dương {1, 2, ..., n}).

• Trong q dòng tiếp theo, dòng thứ i chứa hai số nguyên dương x_i và y_i mô tả truy vấn thứ i (x_i, y_i ≤ n với i = 1, 2, …, q)

Kết quả: Ghi một số nguyên duy nhất là tổng kết quả (câu trả lời) của tất cả các truy vấn.

Ví dụ:

Giải thích: câu trả lời của các truy vấn lần lượt là: 1,2,3,4,-1,-1.

• Tổng của các số trên là: 1 +2 +3 +4 +(-1) +(-1) = 8.

Subtask:

• Subtask 1: 25% số test có n, q ≤ 1000;

• Subtask 2: 25% số test có n ≤ 1000;

• Subtask 3: 25% số test có n, q ≤ 10⁵;

• Subtask 4: 25% số test không có ràng buộc gì thêm.