{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence of $N$ positive integers: $A=(A_1,A_2,\\dots,A_N)$.\nYou will repeat the following operation until the length of $A$ becomes $1$.\n\n*   Let $k$ be the length of $A$ before this operation. Choose integers $i$ and $j$ such that $\\max({A_1,A_2,\\dots,A_{k}})=A_i,\\min({A_1,A_2,\\dots,A_{k}})=A_j$, and $i \\neq j$. Then, replace $A_i$ with $(A_i \\bmod A_j)$. If $A_i$ becomes $0$ at this moment, delete $A_i$ from $A$.\n\nFind the number of operations that you will perform. We can prove that, no matter how you choose $i,j$ in the operations, the total number of operations does not change."},{"iden":"constraints","content":"*   $2 \\le N \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"3\n2 3 6"},{"iden":"sample output 1","content":"3\n\nYou will perform $3$ operations as follows:\n\n*   Choose $i=3,j=1$. You get $A_3=0$, and delete $A_3$ from $A$. Now you have $A=(2,3)$.\n*   Choose $i=2,j=1$. You get $A_2=1$. Now you have $A=(2,1)$.\n*   Choose $i=1,j=2$. You get $A_1=0$, and delete $A_1$ from $A$. Now you have $A=(1)$, and terminate the process because the length of $A$ becomes $1$."},{"iden":"sample input 2","content":"6\n1232 452 23491 34099 57341 21488"},{"iden":"sample output 2","content":"12"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}