{"problem":{"name":"E. Delivery Club","description":{"content":"Petya and Vasya got employed as couriers. During the working day they are to deliver packages to _n_ different points on the line. According to the company's internal rules, the delivery of packages m","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF875E"},"statements":[{"statement_type":"Markdown","content":"Petya and Vasya got employed as couriers. During the working day they are to deliver packages to _n_ different points on the line. According to the company's internal rules, the delivery of packages must be carried out strictly in a certain order. Initially, Petya is at the point with the coordinate _s_1, Vasya is at the point with the coordinate _s_2, and the clients are at the points _x_1, _x_2, ..., _x__n_ in the order of the required visit.\n\nThe guys agree in advance who of them will deliver the package to which of the customers, and then they act as follows. When the package for the _i_\\-th client is delivered, the one who delivers the package to the (_i_ + 1)\\-st client is sent to the path (it can be the same person who went to the point _x__i_, or the other). The friend who is not busy in delivering the current package, is standing still.\n\nTo communicate with each other, the guys have got walkie-talkies. The walkie-talkies work rather poorly at great distances, so Petya and Vasya want to distribute the orders so that the maximum distance between them during the day is as low as possible. Help Petya and Vasya to minimize the maximum distance between them, observing all delivery rules.\n\n## Input\n\nThe first line contains three integers _n_, _s_1, _s_2 (1 ≤ _n_ ≤ 100 000, 0 ≤ _s_1, _s_2 ≤ 109) — number of points of delivery and starting positions of Petya and Vasya.\n\nThe second line contains _n_ integers _x_1, _x_2, ..., _x__n_ — customers coordinates (0 ≤ _x__i_ ≤ 109), in the order to make a delivery.\n\nIt is guaranteed, that among the numbers _s_1, _s_2, _x_1, ..., _x__n_ there are no two equal.\n\n## Output\n\nOutput the only integer, minimum possible maximal distance between couriers during delivery.\n\n[samples]\n\n## Note\n\nIn the first test case the initial distance between the couriers is 10. This value will be the answer, for example, Petya can perform both deliveries, and Vasya will remain at the starting point.\n\nIn the second test case you can optimally act, for example, like this: Vasya delivers the package to the first customer, Petya to the second and, finally, Vasya delivers the package to the third client. With this order of delivery, the distance between the couriers will never exceed 1.\n\nIn the third test case only two variants are possible: if the delivery of a single package is carried out by Petya, the maximum distance between them will be 5 - 2 = 3. If Vasya will deliver the package, the maximum distance is 4 - 2 = 2. The latter method is optimal.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Petya 和 Vasya 被聘为快递员。在工作日，他们需要按特定顺序向直线上的 #cf_span[n] 个不同点派送包裹。根据公司内部规定，派送必须严格按照给定顺序进行。最初，Petya 位于坐标为 #cf_span[s1] 的点，Vasya 位于坐标为 #cf_span[s2] 的点，客户位于坐标为 #cf_span[x1, x2, ..., xn] 的点，顺序为必须访问的顺序。\n\n两人事先约定好谁负责为哪个客户派送包裹，之后他们按如下方式行动：当第 #cf_span[i] 个客户的包裹被派送时，负责派送第 #cf_span[(i + 1)] 个客户包裹的人将出发前往该点（可以是刚去完 #cf_span[xi] 的人，也可以是另一个人）。未参与当前派送的另一个人则原地不动。\n\n为了互相沟通，两人配备了对讲机。但对讲机在距离较远时效果很差，因此 Petya 和 Vasya 希望分配派送任务，使得全天中两人之间的最大距离尽可能小。请帮助 Petya 和 Vasya 在遵守所有派送规则的前提下，最小化两人之间的最大距离。\n\n第一行包含三个整数 #cf_span[n], #cf_span[s1], #cf_span[s2] (#cf_span[1 ≤ n ≤ 100 000], #cf_span[0 ≤ s1, s2 ≤ 109]) — 派送点数量及 Petya 和 Vasya 的初始位置。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] — 客户坐标 (#cf_span[0 ≤ xi ≤ 109])，按派送顺序排列。\n\n保证在数字 #cf_span[s1, s2, x1, ..., xn] 中没有两个相等。\n\n请输出一个整数，表示派送过程中两人之间可能的最小最大距离。\n\n在第一个测试用例中，两人初始距离为 #cf_span[10]。该值即为答案，例如 Petya 可以完成全部两次派送，而 Vasya 保持在初始位置不动。\n\n在第二个测试用例中，你可以最优地行动，例如：Vasya 派送第一个客户，Petya 派送第二个客户，最后 Vasya 派送第三个客户。在这种派送顺序下，两人之间的距离永远不会超过 #cf_span[1]。\n\n在第三个测试用例中，只有两种可能：如果 Petya 派送单个包裹，则两人最大距离为 #cf_span[5 - 2 = 3]；如果 Vasya 派送该包裹，则最大距离为 #cf_span[4 - 2 = 2]。后者更优。\n\n## Input\n\n第一行包含三个整数 #cf_span[n], #cf_span[s1], #cf_span[s2] (#cf_span[1 ≤ n ≤ 100 000], #cf_span[0 ≤ s1, s2 ≤ 109]) — 派送点数量及 Petya 和 Vasya 的初始位置。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] — 客户坐标 (#cf_span[0 ≤ xi ≤ 109])，按派送顺序排列。保证在数字 #cf_span[s1, s2, x1, ..., xn] 中没有两个相等。\n\n## Output\n\n输出一个整数，表示派送过程中两人之间可能的最小最大距离。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，两人初始距离为 #cf_span[10]。该值即为答案，例如 Petya 可以完成全部两次派送，而 Vasya 保持在初始位置不动。在第二个测试用例中，你可以最优地行动，例如：Vasya 派送第一个客户，Petya 派送第二个客户，最后 Vasya 派送第三个客户。在这种派送顺序下，两人之间的距离永远不会超过 #cf_span[1]。在第三个测试用例中，只有两种可能：如果 Petya 派送单个包裹，则两人最大距离为 #cf_span[5 - 2 = 3]；如果 Vasya 派送该包裹，则最大距离为 #cf_span[4 - 2 = 2]。后者更优。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of delivery points.  \nLet $ s_1, s_2 \\in \\mathbb{R} $ be the initial positions of Petya and Vasya.  \nLet $ X = (x_1, x_2, \\dots, x_n) $ be the sequence of delivery coordinates in order.  \n\nLet $ p_i \\in \\{1, 2\\} $ denote which courier (Petya = 1, Vasya = 2) delivers to the $ i $-th client.  \nLet $ P_i \\in \\mathbb{R} $ be the position of courier 1 after delivering the $ i $-th package (or remains at last position if not delivering).  \nLet $ V_i \\in \\mathbb{R} $ be the position of courier 2 after delivering the $ i $-th package (or remains at last position if not delivering).  \n\nInitial state: $ P_0 = s_1 $, $ V_0 = s_2 $.  \nFor each $ i \\in \\{1, \\dots, n\\} $:  \n- If $ p_i = 1 $, then $ P_i = x_i $, $ V_i = V_{i-1} $.  \n- If $ p_i = 2 $, then $ V_i = x_i $, $ P_i = P_{i-1} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100{,}000 $  \n2. $ 0 \\leq s_1, s_2, x_i \\leq 10^9 $ for all $ i $  \n3. All values $ s_1, s_2, x_1, \\dots, x_n $ are distinct.  \n4. The sequence $ p_1, p_2, \\dots, p_n $ is arbitrary in $ \\{1,2\\}^n $.  \n\n**Objective**  \nMinimize the maximum distance between the couriers during the entire process:  \n$$\n\\min_{p_1, \\dots, p_n \\in \\{1,2\\}} \\max_{i \\in \\{0,1,\\dots,n\\}} |P_i - V_i|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF875E","tags":["binary search","data structures","dp"],"sample_group":[["2 0 10\n5 6","10"],["3 2 1\n3 4 5","1"],["1 4 5\n2","2"]],"created_at":"2026-03-03 11:00:39"}}