{"code":"23cdiv2","name":"Chỉnh Sửa Dãy","description":"[user:ami] có một dãy số $A$ độ dài $N$ và một dãy số $B$ gồm $N$ số $0$. Các bạn có thể thực hiện thao tác sau trên dãy $B$ để biến dãy $B$ thành $A$:\r\n- Chọn một cặp $(l, r)$ với $1 ≤ l ≤ r ≤ n$ và một số nguyên $k$. Sau đó, gán $a_i = max(a_i , k)$ với mọi $l ≤ i ≤ r$.\r\n\r\nĐịnh nghĩa \"giá trị cuogma\" của dãy số $A$ chính là số thao tác ít nhất cần thực hiện lên dãy $B$ để biển $B$ thành $A$. Ví dụ, nếu dãy $A$ là [1 2 3] thì giá trị cuogma của dãy số này là 3:\r\n- Chọn cặp (1, 1) và $k$ = 1, dãy $B$ trở thành [1 0 0].\r\n- Chọn cặp (2, 3) và $k$ = 2, dãy $B$ trở thành [1 2 2].\r\n- Chọn cặp (3, 3) và $k$ = 3, dãy $B$ trở thành [1 2 3] - chính là dãy $A$.\r\n\r\nCác bạn cũng có thể thực hiện thao tác sau trên dãy $A$:\r\n- Chọn một chỉ số $i$ với $1 ≤ i ≤ n$ và một số nguyên $x ≥ a_i$. Sau đó, gán $a_i = x$.\r\n \r\nHãy tìm cách thực hiện thao tác trên dãy $A$  **không quá 1 lần** để giá trị cuogma của dãy kết quả là nhỏ nhất có thể và hãy in ra kết quả này.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa 1 số nguyên dương $t$ là số lượng test case.\r\n\r\n- Mỗi test case có dạng sau:\r\n    - Dòng đầu tiên chứa 1 số nguyên dương $N$ là số phần tử của $A$.\r\n    - $N$ dòng tiếp theo chứa, mỗi dòng chứa 1 số nguyên dương biểu thị dãy số $A$.\r\n\r\n#### Output\r\n\r\n- Giá trị cuogma nhỏ nhất của dãy $A$ sau khi thực hiện biến đổi.\r\n\r\n#### Scoring\r\n\r\n- Tất cả test có $1 \\leq t \\leq 3000$.\r\n- Subtask $1$ ($50\\%$ số điểm): $\\sum {N} \\leq 100$ và $a_i$ $\\leq$ $3000$.\r\n- Subtask $2$ ($50\\%$ số điểm): $\\sum {N} \\leq 3000$ và $a_i$ $\\leq$ $3000$.\r\n\r\n#### Example\r\n\r\n!!! question \"Example test\"\r\n    ???+ note \"Sample input\"\r\n        ```\r\n        2\r\n        3\r\n        1\r\n        2\r\n        3\r\n        5\r\n        2 \r\n        2 \r\n        5 \r\n        2\r\n        4\r\n        ```\r\n    ???+ success \"Sample output\"\r\n        ```\r\n        2\r\n        3\r\n        ```\r\n    ??? warning \"Note\"\r\n\r\n        Với a = [1 2 3], ta có thể đổi $a_1$ thành 2, dãy $A$ trở thành [2 2 3]. Sau đó, cần áp dụng 2 thao tác lên dãy $B$ để biến $B$ thành $A$:\r\n        - Chọn cặp (1, 3) và $k$ = 2, dãy $B$ trở thành [2 2 2].\r\n        - Chọn cặp (3, 3) và $k$ = 3, dãy $B$ trở thành [2 2 3].\r\n        \r\n        Với a = [2 2 5 2 4], ta có giữ nguyên dãy. Sau, đó, cần áp dụng 3 thao tác lên dãy $B$ để biến $B$ thành $A$.","points":100.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}