Alice và Bob sống ở hai thế giới riêng biệt. Dù họ khao khát giao tiếp đến đâu, vũ trụ chỉ đáp lại bằng sự im lặng lạnh lùng. Giữa hai thế giới của họ là một vùng biên giới rộng lớn, yên tĩnh, nơi có $n$ cánh cổng cổ đại xếp thành một hàng. Những cánh cổng này đã ngủ yên hàng thiên niên kỷ cho đến một ngày, có lẽ do lời cầu nguyện của Alice và Bob, chúng bắt đầu thức tỉnh.

Cánh cổng thứ $i$ thức tỉnh vào ngày $p_i$. Không có hai cánh cổng nào thức tỉnh cùng ngày; do đó, dãy $p_1,p_2,\ldots,p_n$ là một hoán vị của $\{1,2,\ldots,n\}$.

Một cánh cổng thức tỉnh đơn lẻ chỉ là một vết nứt cô đơn trong thực tại. Nó có thể mang theo một lời thì thầm thoáng qua, nhưng không thể bắc cầu qua khoảng không. Để một đoạn liên tục các cánh cổng tạo thành con đường thực sự cho Alice và Bob, ít nhất hai cánh cổng bên trong nó phải thức tỉnh. Chỉ khi đó không gian giữa các thế giới mới đủ ổn định để thông điệp của họ vượt qua an toàn.

Với mọi chỉ số cổng $i

Bạn được cho $q$ truy vấn. Mỗi truy vấn được xác định bởi một đoạn $[L,R]$. Với mỗi truy vấn, hãy tính tổng các ngày chính xác mà mọi đoạn con liên tục hợp lệ nằm hoàn toàn trong $[L,R]$ lần đầu tiên trở nên có thể mang thông điệp:

$$ \sum_{L \le i < j \le R} \operatorname{sec}(i,j). $$

Nếu $L=R$, không có đoạn nào chứa ít nhất hai cánh cổng, do đó kết quả là $0$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 \le n,q \le 2\cdot 10^5$).

Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\ldots,p_n$ tạo thành một hoán vị của $\{1,2,\ldots,n\}$.

Mỗi dòng trong số $q$ dòng tiếp theo chứa hai số nguyên $L$ và $R$ ($1 \le L \le R \le n$), mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng. Dòng thứ $t$ phải chứa câu trả lời cho truy vấn thứ $t$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

18
10
3
0

Ghi chú

Với truy vấn đầu tiên, các đoạn con có độ dài ít nhất $2$ nằm trong $[1,4]$ có giá trị nhỏ thứ hai lần lượt là $3,3,2,4,2,4$, do đó kết quả là $18$.