贪心

很容易发现后面的数组尽量不要动，所以从后考虑贪心，对于每一个i，贪心到小于$a[i+1]$即可$\\$整体复杂度$o(n)$

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;

题目内容

小红拿到了一个数组，他每次操作可以选择任意一个元素$x$使其变成$\sqrt{x}$(向下取整)。

小红想知道，使得该数组变成非降序，需要至少操作多少次?

输入描述

第一行输入一个正整数$n$，代表数组的元素数量。

第二行输入$n$个正整数$a_i$，代表数组的元素。

$1≤n≤ 10^5$

$1≤ a_i ≤ 10^9$

输出描述

一个整数，代表最少的操作次数。

样例1

输入

3
2 6 3

输出

1

说明

对第二个数操作$1$次即可，数组变成$[2,2,3]$。