Fişierul intrare/ieşire:fotbal3.in, fotbal3.outSursăAlgoritmiada 2018 Runda Finala
AutorEugenie Daniel PosdarascuAdăugată de
Timp execuţie pe test0.3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fotbal3

Fotbalistul profesionist Bossanip a decis sa joace niste fotbal recreational cu grupul sau de N prieteni, fiecare fiind dotat cu o anumita valoare distincta de valoarea oricarui alt prieten.
Mai intai, cei N prieteni se aseaza intr-o linie de la 1 la N, iar apoi Bossanip va alege echipa adversa, formata din orice interval compact de prieteni de ai sai. Cum stim cu totii, in fotbal, precum in viata, conteaza unitatea echipei, lipsa diviziunilor intre cei tari si cei slabi -- iar Bossanip vrea ca echipa adversa sa fie usoara de invins. Astfel, ajutati-l pe Bossanip sa numere cate echipe ar putea selecta unde valoarea membrului cu cea mai mica valoare divide valoarea membrului cu cea mai mare valoare.

Date de intrare

Fişierul de intrare fotbal3.in va contine, pe prima linie, numarul N
Pe cea de a doua linie vom gasi valoarea celor N prieteni, in ordinea in care s-au asezat, separate de spatiu alb.

Date de ieşire

În fişierul de ieşire fotbal3.out se va gasi numarul cerut.

Restricţii

  • 1 ≤ N ≤ 100 000
  • Valorile prietenilor sunt distincte.
  • 1 ≤ valoarea unui prieten ≤ 300 000
  • Pentru teste in valoare de 22 de puncte 1 ≤ N ≤ 1 000

Exemplu

fotbal3.infotbal3.out
6
1 2 3 4 5 6
14
10
25 4 89 200 100 10 8 31 178 40
36

Explicaţie

In primul exemplu, intervalele [1], [2], [3], [4], [5], [6], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5], [1,2,3,4,5,6], [2,3,4], [2,3,4,5,6], [3,4,5,6] satisfac conditia.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?