#P2090. 2024.9.19-MY-第1题-根号数组

2024.9.19-MY-第1题-根号数组

题目内容

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

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

输入描述

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

第二行输入nn个正整数aia_i，代表数组的元素。

1≤n≤1051≤n≤ 10^5

1≤ai≤1091≤ a_i ≤ 10^9

输出描述

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

样例1

输入

3
2 6 3

输出

1

说明

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

知识点:*****

查看知识点以及同类型题目

Statistics