\(a_1,a_2,\dots,a_n\) бүтін сандар массиві берілген. Бір операцияда \(i\) индексін (\(1 \le i \le n\)) және \(x\) бүтін санын (\(1 \le x\)) таңдап, келесі меншіктеуді орындауға болады: \(a_i \leftarrow a_i \bmod x\).

Массив өспейтін емес ретпен сұрыпталған деп аталады, егер \(a_1 \le a_2 \le \dots \le a_n\).

\(\mathrm{score}(b)\) мәнін \(b\) массивін өспейтін емес ретпен сұрыпталған ету үшін қажет ең аз операциялар саны ретінде анықтайық.

Бастапқы \(a\) массивінің барлық ішкімассивтерін \(a_l,a_{l+1},\dots,a_r\) (\(1 \le l \le r \le n\)) қарастырайық. Төмендегі мәнді есептеу қажет: \[\sum_{1 \le l \le r \le n} \mathrm{score}\bigl(a_l,a_{l+1},\dots,a_r\bigr).\]

Енгізу

Бірінші жолда \(n\) бүтін саны берілген (\(1 \le n \le 3 \cdot 10^5\)) — массивтің ұзындығы.

Екінші жолда \(n\) бүтін саны берілген \(a_1,a_2,\dots,a_n\) (\(0 \le a_i \le 10^{12}\)).

Шығару

Бір ғана бүтін санды шығарыңыз — барлық ішкімассивтер үшін \(\mathrm{score}\) мәндерінің қосындысы.

Мысалдар

Енгізу 1

5
5 4 3 2 1

Жауап 1

20

Енгізу 2

5
9 2 8 4 10

Жауап 2

10