DEVARRAY-Devu and an Array

Nguồn: https://www.codechef.com

Devu có một mảng A chứa N số nguyên dương. Anh ta sẽ thực hiện những thao tác sau đây trên mảng này.

§ Chọn hai số a, b trong mảng (a có thể giống với b, nhưng chỉ số tương ứng của hai số đó trong dãy không được giống nhau). Xóa cả hai phần tử a và b và thay vào đó thêm số x với x nằm giữa min(a, b) và max(a, b). (tất là min(a, b) ≤ x ≤ max(a, b)).

Giờ như đã biết sau khi thực hiện thao tác đó N – 1 lần, Devu sẽ chỉ còn lại một số duy nhất trong mảng. Anh đang tự hỏi rằng liệu có thể thực hiện các thao tác theo một cách nào đó mà số cuối cùng là t.

Anh ta nhờ bạn giúp tìm câu trả lời cho Q truy vấn, mỗi truy vấn sẽ chứa một số nguyên t và bạn phải xác định xem liệu có cách nào mảng kết thúc bằng t không.

Dữ liệu vào

Chỉ có một bộ test trong mỗi tập tin dữ liệu.

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên cách nhau bởi khoảng trắng N, Q lần lượt là số lượng phần tử trong A và số lương truy vấn mà Devu nhờ bạn.

Dòng thứ hai chứa N số nguyên cách nhau bởi khoảng trắng là nội dung của mảng A.

Mỗi dòng trong Q dòng tiếp theo sẽ chứa một số nguyên t tương ứng với từng truy vấn.

Dữ liệu ra

Xuất ra Q dòng, mỗi dòng chứa “Yes” hoặc “No” (không có dấu nháy kép) tương ứng với câu trả lời cho mỗi truy vấn.

Ràng buộc

·  1 ≤ N, Q ≤ 10⁵

·  0 ≤ t ≤ 10⁹

Giới hạn

Subtask #1 : 30   điểm

·  1 ≤ Ai ≤ 2

Subtask #2 : 70 điểm

·  1 ≤ Ai ≤ 10⁹

Ví dụ

Input 1:

1 2

1

1

2

Output:

Yes

No

Input 2:

2 4

1 3

1

2

3

4

Output:

Yes

Yes

Yes

No

Giải thích

Trong ví dụ 1, Devu không thể áp dụng bất kỳ thao tác nào. Vì cuối phần tử cuối cùng trong mảng sẽ là 1.

Trong ví dụ 2, Devu có thể thế 1 và 3 với một số bất kỳ giữa 1, 2, 3. Vì vậy kết quả cuối cùng của mảng có thể là 1, 2 hoặc 3.

XÂY DỰNG NHÀ MÁY

GIẤY CHỨNG CHỈ

Steve tham gia rất nhiều kỳ thi, lớp ngoại khóa khác nhau và có đủ các loại chứng chỉ. Các chứng chỉ này được kẹp lưu trữ ở các tập khác nhau không theo một quy tắc nào cả. Cũng may là bên ngoài tập còn ghi số lượng chứng chỉ kẹp trong đó.

Hôm nay Steve cần đi ra văn phòng công chứng sao lại chứng chỉ kết quả thi Tin học Quốc gia để làm hồ sơ xin được tuyển thẳng vào khoa Công nghệ thông tin. Steve chỉ có một chứng chỉ này. Bạn ấy muốn tìm tập chứa chứa chứng chỉ đang cần, mang ra nơi công chứng và trong thời gian xếp hàng chờ đợi sẽ tìm và lấy nó ra để sao. Việc mở một tập kẹp chứng chỉ mất 1 giây, xem xét một chứng chỉ có phải là cái mình đang tìm hay không cũng mất 1 giây. Dĩ nhiên Steve không tìm ở các tập có ghi số lượng là 0. Việc chuyển từ tập này sang tập khác là không đáng kể.

Yêu cầu: Cho n – số tập lưu chứng chỉ và các số a_i – số chứng chỉ lưu trong tập i ( 0 ≤ a_i ≤ 10⁶, 1 ≤ n ≤ 10⁶, i = 1 ÷ n). Hãy xác định, trong trường hợp xấu nhất, Steve cần ít nhất  bao nhiêu thời gian để tìm ra tập cần thiết.

Dữ liệu: Vào từ file văn bản CERTIF.INP:

+ Dòng đầu tiên chứa số nguyên n,

+ Dòng thứ 2 chứa n số nguyên a₁, a₂, . . ., a_n.

Kết quả: Đưa ra file văn bản CERTIF.OUT một số nguyên – thời gian cần để tìm.

Ví dụ:

CERTIF.INP	CERTIF.OUT
4 1 0 2 1	4
3 1 2 3	5

Solution Test