Cho một hoán vị \(p_1, p_2, \ldots, p_n\). Bạn cần trả lời \(q\) truy vấn. Truy vấn thứ \(i\) là một cặp số nguyên \((l_i, r_i)\), bạn cần tính \(f(l_i, r_i)\).

Gọi \(m_{l,r}\) là vị trí của phần tử lớn nhất trong đoạn \(p_l, p_{l+1}, \ldots, p_r\).

nếu \(l \le r\) và bằng \(0\) trong trường hợp ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^6\)) — kích thước của hoán vị \(p\) và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) các số nguyên đôi một phân biệt \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\), \(p_i \ne p_j\ \forall i \ne j\)) — hoán vị \(p\).
• Dòng thứ ba chứa \(q\) số nguyên \(l_1, l_2, \ldots, l_q\) — giá trị \(l\) của các truy vấn.
• Dòng thứ tư chứa \(q\) số nguyên \(r_1, r_2, \ldots, r_q\) — giá trị \(r\) của các truy vấn.
• Đầu vào đảm bảo rằng \(1 \le l_i \le r_i \le n\) cho tất cả các truy vấn.

Output

• In \(q\) số nguyên — các giá trị \(f(l_i, r_i)\) cho các truy vấn tương ứng.

Example

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

1 6 8 5 1

Scoring

• Subtask \(1\) (\(40\%\)): \(1 \le n, q \le 500\)
• Subtask \(2\) (\(30\%\)): \(1 \le n, q \le 5000\)
• Subtask \(3\) (\(20\%\)): Hoán vị được sắp xếp tăng dần hoặc giảm dần
• Subtask \(4\) (\(10\%\)): Giới hạn gốc

Nguồn: Bài 2 ngày 1 đề chọn ĐT HSG QG TP.ĐN 2022-2023