Alice has an array $a$. The array has $N$ positive numbers. She thinks the array is too long, so she wants to shorten the array. She decides to shorten the array via the following operation: every time she will choose an index $i$ $(1 \le i<n)$ which $a_i > 0$ and $a_{i+1} > 0$. She will delete $a_i$ and $a_{i+1}$ and use $(a_i\operatorname{mod} a_{i+1})$ or $(a_{i+1}\operatorname{mod} a_{i})$ to replace them.
For example, for array $[3, 2, 4, 5]$, if Alice choose $i=2$, she can change the array to $[3, 2, 5]$ or $[3, 0, 5]$. Alice wants you to tell her the shortest possible length of the array after several options.