{"code":"querymax3","name":"Query-Max 3","description":"Cho dãy $A$ gồm $N$ phần tử là các số nguyên dương $A_1, A_2, ..., A_N$ ($A_i \\leq 10^9$). Cho $Q$ thao tác thực liện lần lượt, thao tác thứ $i$ sẽ có một trong $4$ loại như sau:\r\n+ $1$ $p_i$ $x_i$: Chèn giá trị $x_i$ vào giữa hai vị trí $p_i - 1$ và $p_i$ trong dãy $A$ ($1 \\leq x_i \\leq 10^9$, $1 \\leq p_i \\leq T + 1$, với $T$ là số phần tử hiện có trong dãy $A$. Nếu $p_i = T + 1$, chèn $x_i$ vào cuối dãy $A$).\r\n+ $2$ $u_i$ $l_i$ $v_i$: Chuyển tất cả các phần tử liên tiếp, bắt đầu từ vị trí $u_i$, kết thúc ở vị trí $u_i + l_i - 1$, chèn vào trước vị trí $v_i$ trong số còn lại ($1 \\leq u_i \\leq T$, $u_i + l_i - 1 \\leq T$ $1 \\leq v_i \\leq T - l_i + 1$, với $T$ là số phần tử hiện có trong dãy $A$. Nếu $v_i = T - l_i + 1$ thì chuyển tất cả các phần tử liên tiếp, bắt đầu từ vị trí $u_i$, kết thúc ở vị trí $u_i + l_i - 1$ vào cuối dãy $A$). \r\n+ $3$ $p_i$: Xoá phần tử ở vị trí $p_i$ ($1 \\leq p_i \\leq T$, với $T$ là số phần tử hiện có trong dãy $A$).\r\n+ $4$ $u_i$ $v_i$: Tìm giá trị lớn nhất trong các phần tử từ vị trí $u_i$ tới vị trí $v_i$ ($1 \\leq u_i \\leq v_i \\leq T$, với $T$ là số phần tử hiện có trong dãy $A$).\r\n\r\n**Yêu cầu** \r\nThực hiện tất cả lần lượt $Q$ thao tác, và in ra kết quả của thao tác loại $4$.\r\n\r\n#### Input\r\n+ Dòng thứ nhất gồm hai số nguyên dương $N, Q$.\r\n+ Dòng thứ hai gồm $N$ số nguyên dương $A_1, A_2, ..., A_N$.\r\n+ $Q$ dòng tiếp theo, với dòng thứ $i$ chứa một trong $4$ thao tác:\r\n    + $1$ $p_i$ $x_i$.\r\n    + $2$ $u_i$ $l_i$ $v_i$.\r\n    + $3$ $p_i$.\r\n    + $4$ $u_i$ $v_i$.\r\n\r\n#### Output\r\n- Với thao tác loại $4$ có dạng $4$ $u$ $v$, in ra giá trị lớn nhất trong các phần tử từ vị trí $u$ tới vị trí $v$.\r\n\r\n#### Scoring\r\n+ Subtask $1$ ($30\\%$ số điểm): $N \\leq 10^3$, $Q \\leq 10^3$.\r\n+ Subtask $2$ ($30\\%$ số điểm): $N \\leq 10^5$, $Q \\leq 10^5$, chỉ có các thao tác loại $4$.\r\n+ Subtask $3$ ($40\\%$ số điểm): $N \\leq 10^5$, $Q \\leq 10^5$.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 6\r\n        2 3 1\r\n        1 3 2\r\n        2 2 1 3\r\n        3 1\r\n        4 1 3\r\n        1 4 5\r\n        4 2 4 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        5\r\n        ```\r\n    ??? warning \"Note\"\r\n\r\n        Nên làm bài [Query-Max 2][1] trước khi làm bài này.\r\n\r\n\r\n  [1]: http://lqdoj.edu.vn/problem/querymax2","points":500.0,"partial":true,"time_limit":1.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}}