Mảng nhọn

Điểm: 3,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho mảng $a_{1}, a_{2}, \dots, a_{n}$ gồm $n$ số nguyên không âm.

Mảng được gọi là nhọn nếu tồn tại chỉ số $1 \leq k \leq n$ sao cho: $a_{1} < a_{2} < \dots < a_{k} và a_{k} > a_{k + 1} > \dots > a_{n} .$

Đặc biệt, mọi mảng tăng nghiêm ngặt hoặc giảm nghiêm ngặt đều là nhọn. Ví dụ, các mảng $[4]$ , $[0, 1]$ , $[12, 10, 8]$ và $[3, 11, 15, 9, 7, 4]$ là nhọn; còn $[2, 8, 2, 8, 6, 5]$ , $[0, 1, 1, 0]$ , $[2, 5, 6, 9, 8, 8]$ thì không.

Bạn được phép thực hiện thao tác sau bao nhiêu lần tùy ý: chọn một phần tử dương bất kỳ của mảng và giảm đi $1$ . Nói cách khác, chọn chỉ số $i$ với $a_{i} > 0$ và gán $a_{i} : = a_{i} - 1$ .

Hãy xác định xem có thể biến mảng đã cho thành mảng nhọn bằng một số (có thể bằng $0$ ) thao tác trên hay không.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.

Với mỗi bộ dữ liệu:

Dòng đầu chứa số nguyên $n$ — độ dài mảng.
Dòng thứ hai chứa $n$ số nguyên không âm $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra Yes nếu có thể biến mảng thành mảng nhọn, ngược lại in No.

Ràng buộc

$1 \leq t \leq 15 000$
$1 \leq n \leq 3 \cdot 10^{5}$
$0 \leq a_{i} \leq 10^{9}$
Tổng $n$ trên tất cả bộ dữ liệu không vượt quá $3 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
10 1 248618 3 12 10 8 6 100 11 15 9 7 8 4 0 1 1 0 2 0 0 2 0 1 2 1 0 2 1 1 3 0 1 0 3 1 0 1	Yes Yes Yes No No Yes Yes Yes Yes No	Bộ 1 và 2: mảng đã nhọn. Bộ 3: có thể biến thành $[3, 11, 15, 9, 7, 4]$ . Bộ 4: không thể đạt được dạng nhọn. Bộ 8 $[1, 1]$ : giảm phần tử đầu hoặc cuối được $[0, 1]$ hoặc $[1, 0]$ , cả hai đều nhọn.
1 5 0 1 2 1 0	Yes	Mảng đã nhọn với đỉnh ở $k = 3$ .
1 5 0 0 0 0 0	No	Tất cả phần tử bằng $0$ , không thao tác nào tăng được giá trị nên không thể tạo dạng nhọn cho $n \geq 3$ .

Bình luận

Không có bình luận tại thời điểm này.