{"problem":{"name":"J. Joseph and Tests","description":{"content":"Joseph developed a device that allows people to decrease or increase their height by at most $D$ units. He's playing with his friend Lucas on a circuit with N houses, numbered from $1$ to $N$, on whic","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10202J"},"statements":[{"statement_type":"Markdown","content":"Joseph developed a device that allows people to decrease or increase their height by at most $D$ units. He's playing with his friend Lucas on a circuit with N houses, numbered from $1$ to $N$, on which Lucas can only get inside if his height is exactly equal to the height of the door of the house he's trying to get in. There will be two types of queries:\n\n1. There will be given two integers $i$ and $X$, meaning that the i-th house's height is now equal to $X$;\n\n2. There will be given two integers $L$ and $D$, meaning that Joseph's device can only increase or decrease someone's height by at most $D$ units, and that Lucas will walk sequentially through the circuit, starting with height equal to $A [ L ]$, on the $L$-th house, until he finishes the circuit or encounters a house where he can't get in. For each query of this type, you must answer on which house he will stop. Note that Lucas can only go to house $i + 1$ from the house $i$ if $| A [ i + 1 ] -A [ i ] | <= D$.\n\nThe first line contains one integer $N$ $(1 <= N <= 2 * 10^5)$, representing the number of houses on the circuit. The second line contains $N$ integers $A_i$ $(1 <= A_i <= 2 * 10^5)$, where $A_i$ is the height of the door of the $i$-th house. The third line contains a single integer $Q$ $(1 <= Q <= 2 * 10^5)$, the number of queries. Then, $Q$ lines follow, each of them containing three integers: $t_i$ $(1 <= t_i <= 2)$, $a_i$ and $b_i$ $(1 <= a_i <= N, \" \"1 <= b_i <= 2 * 10^5)$. $t_i$ stands for the type of $i$-th query, and $a_i$ and $b_i$ are the $i$-th query's parameters, according to the description on the problem's statement.\n\nFor each query of the second type, output one line containing a single integer, representing the number of the house where Lucas will finish his walk.\n\n## Input\n\nThe first line contains one integer $N$ $(1 <= N <= 2 * 10^5)$, representing the number of houses on the circuit. The second line contains $N$ integers $A_i$ $(1 <= A_i <= 2 * 10^5)$, where $A_i$ is the height of the door of the $i$-th house. The third line contains a single integer $Q$ $(1 <= Q <= 2 * 10^5)$, the number of queries. Then, $Q$ lines follow, each of them containing three integers: $t_i$ $(1 <= t_i <= 2)$, $a_i$ and $b_i$ $(1 <= a_i <= N, \" \"1 <= b_i <= 2 * 10^5)$. $t_i$ stands for the type of $i$-th query, and $a_i$ and $b_i$ are the $i$-th query's parameters, according to the description on the problem's statement.\n\n## Output\n\nFor each query of the second type, output one line containing a single integer, representing the number of the house where Lucas will finish his walk.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of carpets, $ m \\in \\mathbb{Z} $ be the grid size.  \n- Let $ C = \\{ c_i = (x_{l,i}, x_{r,i}, y_{l,i}, y_{r,i}) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of carpets, where each $ c_i $ denotes a rectangular region covering rows $[x_{l,i}, x_{r,i}]$ and columns $[y_{l,i}, y_{r,i}]$.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. $ 3 \\le n \\le 3 \\times 10^5 $, $ 1 \\le m \\le 1500 $  \n3. For each carpet $ c_i $: $ 1 \\le x_{l,i} \\le x_{r,i} \\le m $, $ 1 \\le y_{l,i} \\le y_{r,i} \\le m $  \n4. Sum of $ n $ over all test cases $ \\le 2 \\times 10^6 $  \n5. Sum of $ m^2 $ over all test cases $ \\le 5 \\times 10^7 $  \n\n**Objective**  \nSelect two carpets $ c_i, c_j \\in C $ ($ i \\ne j $) to remove such that the area covered by the union of the remaining $ n-2 $ carpets is minimized.  \nLet $ U(S) = \\left| \\bigcup_{c_k \\in S} c_k \\right| $ denote the number of unit tiles covered by the union of carpets in set $ S $.  \nCompute:  \n$$\n\\min_{\\substack{i,j \\in \\{1,\\dots,n\\} \\\\ i \\ne j}} U(C \\setminus \\{c_i, c_j\\})\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10202J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}