{"problem":{"name":"H. Gas Stations","description":{"content":"The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. *All of them are populated by citizens*, and some of them has gas stations. People in each block wi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10160H"},"statements":[{"statement_type":"Markdown","content":"The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. *All of them are populated by citizens*, and some of them has gas stations. People in each block will go to the nearest block that has a gas station. The distance between two blocks i and j is |i - j|, where |x| is the absolute value of x.\n\nThe government wants to move at most one station from its original block to another block. What is the maximum distance that a citizen has to cross to get to his/her nearest station, if the government operated in a way that minimizes this distance?\n\nThe first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.\n\nThe first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.\n\nThe second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.\n\nIt is guaranteed that there’s at least one block that has a gas station.\n\nThe total sum of n overall test cases doesn't exceed 5 × 106.\n\nFor each test case, print the answer on a single line.\n\n## Input\n\nThe first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.The first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.The second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.It is guaranteed that there’s at least one block that has a gas station.The total sum of n overall test cases doesn't exceed 5 × 106.\n\n## Output\n\nFor each test case, print the answer on a single line.\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 $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of blocks.  \n- Let $ s_k \\in \\{+,\\ .\\}^{n_k} $ be a string representing the city, where $ s_k[i] = '+' $ if block $ i $ has a gas station, and $ s_k[i] = '.' $ otherwise.  \n- Let $ G_k = \\{ i \\in \\{1, \\dots, n_k\\} \\mid s_k[i] = '+' \\} $ be the set of blocks with gas stations.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1200 $  \n2. $ 1 \\le n_k \\le 10^5 $ for each $ k $  \n3. $ |G_k| \\ge 1 $ for each $ k $  \n4. $ \\sum_{k=1}^T n_k \\le 5 \\times 10^6 $  \n\n**Objective**  \nLet $ d(i) = \\min_{g \\in G_k} |i - g| $ be the distance from block $ i $ to its nearest gas station.  \nLet $ D_k = \\max_{i \\in \\{1, \\dots, n_k\\}} d(i) $ be the maximum distance any citizen must travel.  \n\nThe government may move **at most one** gas station from its current block to any other block (possibly empty), i.e., replace one element $ g \\in G_k $ with some $ g' \\in \\{1, \\dots, n_k\\} \\setminus G_k $, or leave $ G_k $ unchanged.  \n\nFind the **minimum possible value of $ D_k $** after such a move.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10160H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}