El famoso club Bananitas FC, cansado de perder partidos y sin lograr su primera victoria, decidió viajar a Cabo Verde para mejorar su nivel de juego. Sin embargo, el dinero es un problema y deben arreglárselas solos como siempre, así que los jugadores optaron por adentrarse en el mundo de la programación para financiar el viaje.

Como parte de una entrevista técnica para conseguir su primer trabajo, les plantearon el siguiente problema:

Dado un array de enteros positivos ($A$). En una operación puedes elegir un índice $i$ y reemplazar $a_i$ por $a_i^2$ o por $\lfloor\sqrt{a_i}\rfloor$. Puedes aplicar estas operaciones tantas veces como desees. Calcula el mínimo número de operaciones necesarias para que el arreglo quede ordenado de forma no decreciente y que se cumpla $1 \le a_i \le 10^{18}$ en todo momento.

Lamentablemente, ninguno de los jugadores tiene el nivel necesario para resolverlo. Aun así, mantienen la esperanza de que algún participante de la competencia interna de la UMSA pueda ayudarlos. ¿Podrás resolver el problema y acercar a Bananitas FC a su sueño Cabo Verdiano?

• La primera línea contiene un entero $N$ ($1 \le N \le 10^5$): la cantidad de elementos del array.
• La segunda línea contiene $N$ enteros $a_i$ ($1 \le a_i \le 10^{18}$).

La cantidad mínima de operaciones necesarias para que el arreglo quede ordenado de forma no decreciente, cumpliendo en todo momento que $1 \le a_i \le 10^{18}$.