{"code":"23on4c24","name":"Thao Tác","description":"Cho số nguyên dương $N$ và dãy số nguyên không âm $x_1,x_2,...,x_N$. Ban đầu tất cả các phần tử trong dãy $x$ đều bằng $0$.\r\n\r\nĐức có thể dùng hai thao tác sau bao nhiêu lần tùy ý và theo bất kì thứ tự tùy ý:\r\n\r\n - Thao tác $1$: Cho một số nguyên dương $k$ $(1 \\le k \\le N)$, tạo dãy số **không giảm** gồm $k$ số nguyên không âm $r_1,r_2,...,r_k$. Với mọi $1 \\le i \\le k$ ta sẽ thay $x_i$ bằng $x_i + r_i$.\r\n - Thao tác $2$: Cho một số nguyên dương $k$ $(1 \\le k \\le N)$, tạo dãy số **không tăng** gồm $k$ số nguyên không âm $r_1,r_2,...,r_k$. Với mọi $1 \\le i \\le k$ ta sẽ thay $x_{N-k+i}$ bằng $x_{N-k+i} + r_i$.\r\n\r\n**Yêu cầu:** Cho dãy số nguyên dương có $N$ số nguyên dương $a_1,a_2,...,a_N$ được nhập từ bàn phím. Bạn hãy tìm và in ra số lần thao tác ít nhất để dãy $x$ trùng với dãy $a$, biết rằng hai dãy $x$ và $a$ được gọi là trùng nhau khi với mọi $1 \\le i \\le N$ thì $x_i = a_i$.\r\n\r\n#### Input\r\n - Dòng đầu tiên chứa số nguyên dương $N$ $(1 \\le N \\le 2 \\times 10^5)$.\r\n - Dòng tiếp theo chứa dãy số $a_1,a_2,...,a_N$ $(1 \\le a_i \\le 10^9)$.\r\n\r\n#### Output\r\n - In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài\r\n\r\n#### Scoring\r\n - Subtask $1$ ($50\\%$ số điểm): Có $1 \\le N \\le 1000$ và các phần tử trong dãy $a$ không quá $5000$.\r\n - Subtask $2$ ($50\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        1 2 1 2 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Có một cách để đạt được yêu cầu đề bài với $3$ thao tác, ta sẽ làm như sau:\r\n               - Thực hiện thao tác $1$ và cho $k = 2$, $r = (1,2)$. Lúc này $x = (1,2,0,0,0)$.\r\n               - Thực hiện thao tác $1$ và cho $k = 3$, $r = (0,0,1)$. Lúc này $x = (1,2,1,0,0)$.\r\n               - Thực hiện thao tác $2$ và cho $k = 2$, $r = (2,1)$. Lúc này $x = (1,2,1,2,1)$ trùng với dãy $a$ thỏa mãn yêu cầu đề bài.","points":2000.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[34,36,37,5,6,11,12,28,38,39,29,27,35,10,32,1,8,15,16,33,41,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}