{"problem":{"name":"E. Extreme Permutations","description":{"content":"#cf_span(class=[tex-font-style-underline], body=[Permutation]) of length n is called the sequence of n integers, containing each of integers between 1 and n exactly once. For example, (3, 4, 5, 1, 2) ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10091E"},"statements":[{"statement_type":"Markdown","content":"#cf_span(class=[tex-font-style-underline], body=[Permutation]) of length n is called the sequence of n integers, containing each of integers between 1 and n exactly once. For example, (3, 4, 5, 1, 2) and (1, 2) are permutations, (1, 4, 3) and (2, 1, 3, 2) are not.\n\nLets call the permutation #cf_span(class=[tex-font-style-underline], body=[extreme]), if for any two neighbor numbers in the permutation difference between them is not less than minimum of those 2 numbers. For example, permutation (3, 1, 2, 4) is extreme, because |3 - 1| ≥ min(3, 1), |1 - 2| ≥ min(1, 2) and |2 - 4| ≥ min(2, 4).\n\nGiven an #cf_span(class=[tex-font-style-underline], body=[odd]) n, calculate number of the extreme permutations of length n where positions of some integers are fixed.\n\nFirst line of the input contains one integer n — length of permutation (1 ≤ n ≤ 27, n = 2k + 1 for some integer k).\n\nSecond line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n). If pi is equal to 0, then i-th position is not fixed, otherwise on i-th position must stay pi. You may assume that if pi > 0 and pj > 0 for 1 ≤ i, j ≤ n, i ≠ j, then pi ≠ pj.\n\nPrint one integer — number of the extreme permutations where all fixed elements are on their positions.\n\n## Input\n\nFirst line of the input contains one integer n — length of permutation (1 ≤ n ≤ 27, n = 2k + 1 for some integer k).Second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n). If pi is equal to 0, then i-th position is not fixed, otherwise on i-th position must stay pi. You may assume that if pi > 0 and pj > 0 for 1 ≤ i, j ≤ n, i ≠ j, then pi ≠ pj.\n\n## Output\n\nPrint one integer — number of the extreme permutations where all fixed elements are on their positions.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an odd integer such that $ n = 2k + 1 $ for some $ k \\in \\mathbb{Z}_{\\geq 0} $, and $ 1 \\leq n \\leq 27 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a partial permutation where $ p_i \\in \\{0\\} \\cup \\{1, 2, \\dots, n\\} $, and if $ p_i > 0 $ and $ p_j > 0 $ for $ i \\neq j $, then $ p_i \\neq p_j $.  \nA full permutation $ \\sigma = (\\sigma_1, \\sigma_2, \\dots, \\sigma_n) $ of $ \\{1, 2, \\dots, n\\} $ is called **extreme** if for all $ i \\in \\{1, 2, \\dots, n-1\\} $:  \n$$\n|\\sigma_i - \\sigma_{i+1}| \\geq \\min(\\sigma_i, \\sigma_{i+1})\n$$\n\n**Constraints**  \n1. $ n $ is odd, $ 1 \\leq n \\leq 27 $.  \n2. For each $ i \\in \\{1, \\dots, n\\} $:  \n   - $ p_i = 0 $: position $ i $ is free.  \n   - $ p_i > 0 $: $ \\sigma_i = p_i $ (fixed).  \n3. All fixed values $ p_i > 0 $ are distinct.  \n\n**Objective**  \nCount the number of extreme permutations $ \\sigma $ of length $ n $ satisfying $ \\sigma_i = p_i $ for all $ i $ where $ p_i > 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10091E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}