Počet bodov:
Popis:  12b
Program:  8b

Adam, Buj, Cecília1 a Dávid nedávno zistili, že každému z nich chýba nejaký kus elektroniky. Adamovi chýba server, Bujovi lietajúci dron, Cecílii elektrická zubná kefka a Dávidovi obrazovka s ešte väčším rozlíšením, ako má teraz. Čo teda spravili? Išli na stránku Internetového obchodu s najotravnejšou reklamou na svete2 a objednali si, čo potrebovali.

I nastal deň, keď si všetci štyria mali vyzdvihnúť svoju objednávku. Prišli preto do centrály IONRS, zaplatili a každý z nich dostal papierik, na ktorom bolo napísané nejaké číslo a ich meno3. Následne sa zaradili do množstva ľudí čakajúcich na výdaj. V IONRS to totiž funguje tak, že objednané (a už zaplatené) predmety prichádzajú zo skladu na bežiacom páse, kde ich zloží šikovná pracovníčka, vyhlási číslo a meno priradené k danému predmetu a príslušný človek si ho ide zobrať.

Naši štyria kamaráti teda počúvali vyvolávané čísla a čakali, kedy odznie to ich. Ako prvý prišiel na rad Adam so svojím serverom. O niečo neskôr bolo vyvolané Bujove číslo a on si radostne začal rozbaľovať svojho drona. Keď už dron lietal, prišla po páse Cecíliina zubná kefka a posledný prišiel na rad Dávid.

Keď sa vracali z tohto výletu, stretli na ulici vešticu, a tá sa ich spýtala, aké čísla mali v IONRS na papierikoch. Tvrdila totiž, že sa podľa toho dá odhadnúť ich budúcnosť. Ak by v tom čísle boli samé štvorky a sedmičky, mali by nesmierne šťastie, pokiaľ ale spomenuté číslo bolo deliteľné trinástkou, nemuselo by to pre nich dopadnúť práve najlepšie.

Naši hrdinovia však zistili, že si svoje čísla nepamätajú a papieriky odovzdali, keď si vyzdvihovali nákup. Pamätali si len, že súčin Adamovho a Bujovho čísla bol rovnaký, ako súčin Cecíliinho a Dávidovho. Na internete sa tiež dá pozrieť zoznam čísel vyhlásených v daný deň, samozrejme už bez priradených mien a predmetov. Teraz by chceli vedieť, koľko takých štvoríc čísel zo zoznamu mohlo patriť im. Ak by tam bola len jedna, bolo by to jasné…

Úloha

Na vstupe dostanete postupnosť \(n\) čísel, označme si ich postupne \(x_1\)\(x_n\). Nájdite počet všetkých rôznych štvoríc \((a,b,c,d)\), pre ktoré platí, že

  • \(x_a \cdot x_b = x_c \cdot x_d\)
  • \(1 \leq a < b < c < d \leq n\)

(\(a\), \(b\), \(c\), \(d\) vyjadrujú pozíciu Adamovho, Bujovho, Cecíliinho a Dávidovho čísla v zozname.)

Formát vstupu

Na prvom riadku je číslo \(n ~ (1 \leq n \leq 1\,000)\) – počet čísel v postupnosti.

Na druhom riadku sa nachádza \(n\) čísel oddelených medzerou, \(x_1\)\(x_n\), čiže jednotlivé čísla, ktoré boli vyhlásené v IONRS. Platí, že \(0\leq x_i\leq 10^9\).

Formát výstupu

Na výstup vypíšte jedno číslo – počet takých štvoríc \(a\), \(b\), \(c\) a \(d\), že \(x_a\cdot x_b = x_c \cdot x_d\) a \(1 \leq a < b < c < d \leq n\).

Príklady

Input:

5
1 12 3 4 3

Output:

2

Buď mali čísla \(1,12,3,4\) alebo \(1,12,4,3\).

Input:

6
1 1 1 1 1 1

Output:

15

Ľubovoľná štvorica spĺňa \(x_a \cdot x_b = x_c \cdot x_d\)

Input:

10
1 2 3 4 5 6 7 8 9 10

Output:

0

Ak by boli vyhlásené tieto čísla, tak určite \(x_a \cdot x_b < x_c \cdot x_d\)


  1. Naozaj neexistuje KSPák, ktorého meno sa začína na C.

  2. Ďalej len IONRS.

  3. Keby náhodou prišli do predajne ľudia s rovnakým menom, treba ich odlíšiť číslami.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.