{"problem":{"name":"A. Pride","description":{"content":"You have an array _a_ with length _n_, you can perform operations. Each operation is like this: choose two **adjacent** elements from _a_, say _x_ and _y_, and replace one of them with _gcd_(_x_, _y_)","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF891A"},"statements":[{"statement_type":"Markdown","content":"You have an array _a_ with length _n_, you can perform operations. Each operation is like this: choose two **adjacent** elements from _a_, say _x_ and _y_, and replace one of them with _gcd_(_x_, _y_), where _gcd_ denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).\n\nWhat is the minimum number of operations you need to make all of the elements equal to 1?\n\n## Input\n\nThe first line of the input contains one integer _n_ (1 ≤ _n_ ≤ 2000) — the number of elements in the array.\n\nThe second line contains _n_ space separated integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the elements of the array.\n\n## Output\n\nPrint _\\-1_, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.\n\n[samples]\n\n## Note\n\nIn the first sample you can turn all numbers to 1 using the following 5 moves:\n\n*   \\[2, 2, 3, 4, 6\\].\n*   \\[2, 1, 3, 4, 6\\]\n*   \\[2, 1, 3, 1, 6\\]\n*   \\[2, 1, 1, 1, 6\\]\n*   \\[1, 1, 1, 1, 6\\]\n*   \\[1, 1, 1, 1, 1\\]\n\nWe can prove that in this case it is not possible to make all numbers one using less than 5 moves.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你有一个长度为 $n$ 的数组 $a$，你可以执行操作。每个操作如下：选择数组 $a$ 中两个相邻的元素，记为 $x$ 和 $y$，并将其中一个替换为 $\\gcd(x, y)$，其中 $\\gcd$ 表示最大公约数。\n\n请问，最少需要多少次操作，才能使所有元素都变为 $1$？\n\n输入的第一行包含一个整数 $n$（$1 \\leq n \\leq 2000$）——数组中元素的个数。\n\n第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \\dots, a_n$（$1 \\leq a_i \\leq 10^9$）——数组的元素。\n\n如果不可能将所有数变为 $1$，请输出 _-1_；否则，请输出使所有数都等于 $1$ 所需的最少操作次数。\n\n在第一个样例中，你可以使用以下 $5$ 步操作将所有数变为 $1$：\n\n我们可以证明，在这种情况下，不可能用少于 $5$ 步操作使所有数都变为 $1$。\n\n## Input\n\n输入的第一行包含一个整数 $n$（$1 \\leq n \\leq 2000$）——数组中元素的个数。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \\dots, a_n$（$1 \\leq a_i \\leq 10^9$）——数组的元素。\n\n## Output\n\n如果不可能将所有数变为 $1$，请输出 _-1_；否则，请输出使所有数都等于 $1$ 所需的最少操作次数。\n\n[samples]\n\n## Note\n\n在第一个样例中，你可以使用以下 $5$ 步操作将所有数变为 $1$： $[2, 2, 3, 4, 6]$。 $[2, 1, 3, 4, 6]$ $[2, 1, 3, 1, 6]$ $[2, 1, 1, 1, 6]$ $[1, 1, 1, 1, 6]$ $[1, 1, 1, 1, 1]$ 我们可以证明，在这种情况下，不可能用少于 $5$ 步操作使所有数都变为 $1$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i \\in \\mathbb{Z}^+ $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nDetermine the minimum number of operations required to transform all elements of $ A $ into $ 1 $, where each operation consists of:  \n- Selecting two adjacent elements $ a_i, a_{i+1} $,  \n- Replacing either $ a_i $ or $ a_{i+1} $ with $ \\gcd(a_i, a_{i+1}) $.  \n\nIf it is impossible to make all elements equal to $ 1 $, output $ -1 $.  \n\n**Key Insight**  \nIt is impossible if and only if $ \\gcd(a_1, a_2, \\dots, a_n) \\neq 1 $.  \nOtherwise, the minimum number of operations is:  \n$$\nn - \\text{(length of the longest contiguous subarray with GCD } = 1) + (\\text{number of } 1\\text{s already present}) - 1\n$$  \nEquivalently, let $ m $ be the minimum number of adjacent GCD operations required to produce a single $ 1 $ anywhere in the array. Then the total operations needed is:  \n$$\nm + (n - 1)\n$$  \nwhere $ m $ is the minimal number of operations to create a $ 1 $ from some contiguous subarray.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF891A","tags":["brute force","dp","greedy","math","number theory"],"sample_group":[["5\n2 2 3 4 6","5"],["4\n2 4 6 8","\\-1"],["3\n2 6 9","4"]],"created_at":"2026-03-03 11:00:39"}}