Chia dãy

Điểm: 0,30 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Tác giả:

hohohaha, DatVu, LptN21

, quangminh_0604

, ducanh2706, trnthienphc2003

, marvinthang

, huyhasun

, Ddoraaaaa

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy $a_{1}, a_{2}, \dots, a_{n}$ gồm $n$ số nguyên. Bạn cần trả lời $q$ truy vấn, mỗi truy vấn gồm hai số nguyên $l$ , $r$ . Với mỗi truy vấn bạn cần đếm xem, có bao nhiêu cách chia dãy $a_{l}, a_{l + 1}, \dots, a_{r}$ thành hai phần khác rỗng sao cho mỗi phần gồm các phần tử đứng liên tiếp và đôi một phân biệt.

Input

Dòng đầu chứa hai số nguyên $n$ , $q$ ( $1 \leq n, q \leq 5 \times 10^{5}$ ).

Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

$q$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_{i}$ , $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ ) mô tả truy vấn thứ $i$ .

Output

In ra $q$ dòng, dòng thứ $i$ gồm một số nguyên là kết quả cho truy vấn thứ $i$ .

Sample Input 1

Copy

8 4
1 3 2 2 4 5 4 6
1 8
1 4
2 7
4 6

Sample Output 1

Copy

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

nongquan đã bình luận 3:07:28 ch, 06/03/2025

thuật đơn giản:https://ideone.com/5EPVWj