小红的元素分裂
题号:NC263086
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个数组,她每次可以进行如下操作之一:
·选择一个元素x,将其分裂为1x-1
·选择一个元素x,将其分裂为ab,需要保证a*b=x

小红希望用最少的操作次数,将所有数组的所有元素全部变成1。你能帮帮她吗?

输入描述:

第一行输入一个正整数n,代表数组的长度。
第二行输入n个正整数a_i,代表小红拿到的数组。
1\leq n,a_i \leq 10^5

输出描述:

一个整数,代表最小的操作次数。
示例1

输入

复制
2
2 6

输出

复制
5

说明

第一次,对第一个元素进行第一个操作,数组变成[1,1,6]。
第二次,对第三个元素进行第二个操作,数组变成[1,1,2,3]。
第三次,对第三个元素进行第一个操作,数组变成[1,1,1,1,3]。
第四次,对第五个元素进行第一个操作,数组变成[1,1,1,1,2,1]。
第五次,对第五个元素进行第一个操作,数组变成[1,1,1,1,1,1,1]。