Bedao Grand Contest 10 - PERFECT

View as PDF

Submit solution


Points: 0.55 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một dãy số ~b_1, b_2, \ldots, b_k~ được gọi là hoàn hảo nếu các phần tử của dãy ~b~ tạo thành một dãy số nguyên liên tiếp khi sắp xếp tăng dần.

Cho hoán vị ~p_1, p_2, \ldots, p_n~ và ~q~ truy vấn có dạng ~(l, r)~, hãy cho biết dãy con ~p_l, p_{l + 1}, \ldots, p_r~ có phải là dãy số hoàn hảo hay không?

Input

Dòng đầu tiên gồm số nguyên ~n~ (~1 \le n \le 10^5~) — độ dài của hoán vị ~p~ và ~q~ (~1 \le q \le 10^5~) — số truy vấn của bài toán.

Dòng thứ hai gồm ~n~ số nguyên dương ~p_1, p_2, \ldots, p_n~ (~1 \le p_i \le n~) thể hiện hoán vị ~p~ độ dài ~n~.

~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~(l_i, r_i)~ (~1 \le l_i \le r_i \le n~) thể hiện một truy vấn của bài toán.

Output

Gồm ~q~ dòng, dòng thứ ~i~ in ra YES nếu dãy con ~p_{l_i}, p_{l_i + 1}, \ldots, p_{r_i}~ là một dãy số hoàn hảo; ngược lại in ra NO.

Subtask

  • ~30\%~ số test có ~n \le 300~.

  • ~30\%~ số test khác có ~n \le 5000~.

  • ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

NO
YES
NO
YES

Notes

Ở truy vấn thứ nhất, dãy con ~[1, 2, 5]~ không phải là dãy số hoàn hảo.

Ở truy vấn thứ hai, dãy con ~[2, 5, 3, 4]~ là dãy số hoàn hảo vì khi sắp xếp lại, ta nhận được dãy ~[2, 3, 4, 5]~ là một dãy số nguyên liên tiếp.

Ở truy vấn thứ ba, dãy con ~[1, 2, 5, 3]~ không phải là dãy số hoàn hảo vì khi sắp xếp lại, ta nhận được dãy ~[1, 2, 3, 5]~ không phải là dãy số nguyên liên tiếp.

Ở truy vấn thứ tư, dãy con ~[5]~ là dãy số hoàn hảo.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.