Chán chường

Cho một lưới ô vuông kích thước $n\times n$. Trên lưới có đúng $n$ ô được đánh dấu sao cho không có hai ô đánh dấu nào cùng hàng hoặc cùng cột. Cụ thể, ở cột $i$ có đúng một ô được đánh dấu, nằm ở hàng $p_i$. Các hàng được đánh số từ $1$ đến $n$ theo chiều từ dưới lên trên, các cột được đánh số từ $1$ đến $n$ theo chiều từ trái sang phải.

Ta gọi một hình chữ nhật có các cạnh song song với cạnh lưới là đẹp nếu đúng hai trong bốn ô ở góc của nó là ô được đánh dấu. Có đúng $\frac{n(n-1)}{2}$ hình chữ nhật đẹp (mỗi cặp ô đánh dấu xác định duy nhất một hình chữ nhật đẹp nhận hai ô đó làm hai góc đối diện).

Cho $q$ hình chữ nhật truy vấn (không nhất thiết là hình chữ nhật đẹp), với mỗi hình chữ nhật truy vấn hãy tìm độ đẹp của nó. Độ đẹp của một hình chữ nhật là số hình chữ nhật đẹp có chung ít nhất một ô với hình chữ nhật đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$: kích thước lưới và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$ (tất cả đôi một khác nhau): ở cột $i$ có ô đánh dấu tại hàng $p_i$.
• $q$ dòng tiếp theo, mỗi dòng mô tả một hình chữ nhật truy vấn bằng bốn số nguyên $l,d,r,u$: $l$ và $r$ là cột trái nhất và cột phải nhất, $d$ và $u$ là hàng dưới nhất và hàng trên nhất của hình chữ nhật.

Dữ liệu ra

Với mỗi truy vấn, in ra độ đẹp của hình chữ nhật đó trên một dòng riêng.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le q\le 2·{10}^5$
• $1\le p_i\le n$, các $p_i$ đôi một khác nhau
• $1\le l\le r\le n$, $1\le d\le u\le n$

Ví dụ