TLEoj Contest #01 - Cặp số đầy đủ

Điểm: 2300 (thành phần)

Thời gian: 0.5s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Bạn được cho một hoán vị $a$ độ dài $n$ . Một cặp số $(l,r)$ được gọi là cặp số đầy đủ nếu với mọi $l\le i\le r$ thì $l\le a_i\le r$ .

Bạn được cho $q$ truy vấn, mỗi truy vấn gồm 2 số $l,r$ . Nhiệm vụ của bạn là với mỗi truy vấn, hãy đếm số lượng cặp số $(u,v)\ (l\le u\le v\le r)$ thỏa mãn $(u,v)$ là cặp số đầy đủ

Input, Output và Subtasks

Input

Dòng đầu tiên gồm 2 số nguyên dương $n$ và $q$ $(1 \le n,q \le 10^5)$ .
Dòng tiếp theo gồm $n$ số nguyên dương $a_1,a_2,\dots,a_n\ (1\le a_i\le n)$ . Các giá trị $a_i$ đôi một phân biệt
$q$ dòng tiếp theo, mỗi dòng gồm 2 giá trị $l,r$ ( $1\le l\le r\le n$ )

Output

Với mỗi truy vấn, xuất ra kết quả tương ứng trong một dòng

Subtasks

Subtask 1 $(25\%)$ : $n\le 1000$ .
Subtask 2 $(25\%)$ : $q=1,l=1,r=n$
Subtask 3 $(50\%)$ : Không có ràng buộc gì thêm

Sample

Input

Output

Note

Các cặp số đầy đủ: $(1,1), (1,2), (1,4), (2,2), (2,4), (3,4)$

Bình luận

Không có bình luận nào.