Malá neznáma firma (so sídlom kdesi v Karlovke) rada fušuje do rôznych meteorologických záležitostí. Najnovšie vymysleli senzor, ktorým vedia odmerať teplotu vzduchu v ľubovoľnej výške nad daným bodom.
Keby sme sa v bežný deň postavili na daný bod a začali sa hýbať dohora, bol by vzduch okolo nás čím ďalej, tým chladnejší. Občas to tak ale nie je. Takúto situáciu voláme teplotná inverzia.
Samozrejme, úloha programovať tento senzor padla na krk Janke, ktorá je od radosti celá bez seba. Prvá vec, ktorú potrebuje spraviť, je rozpoznávať a charakterizovať teplotné inverzie. Ako dáta zo senzoru dostane postupnosť teplôt vzduchu, nameraných v rôznych výškach. Keby bol senzor presný, ľahko by mohla definovať, že teplotná inverzia je tým väčšia, čím je v dátach viac dvojíc teplôt, ktoré sú opačne – t. j. vyššie nameraná teplota je vyššia.
Senzor však má od dokonalosti ďaleko. Experimenty naznačujú, že jeho merania sa pohybujú v rámci vhodnej relatívnej chyby od presnej hodnoty. Janka preto na základe nameraných dát odhadla magickú konštantu k≥1 a rozhodla sa, že za prehodenú dvojicu bude považovať len takú, kde je vyššia teplota aspoň k-krát vyššia od tej nižšej. Hlavný problém stojí však stále pred ňou, a správne tušíte, že aj pred vami. Napísať program, ktorý pre dané dáta a magickú konštantu poráta, koľko rôznych dvojíc teplôt je vymenených.
Nasledujúci odsek nemá vplyv na riešenie. Formálne detaily o chybe senzora. Nech je presná hodnota teploty T. Potom senzor vráti číslo z intervalu [T/q,Tq] pre nejaké vhodné q>1. Potom keď zoberieme k=q2, môžeme z istotou prehlásiť, že ak je z dvoch nameraných hodnôt jedna viac ako k-krát väčšia, je zo zodpovedajúcich skutočných hodnôt tá prvá určite väčšia.
V prvom riadku vstupu sú dve prirodzené čísla p, q oddelené medzerou. Platí k=p/q a 1 000 000 000 ≥ p ≥ q ≥ 1.
V druhom riadku je jedno prirodzené číslo N, udávajúce počet nameraných teplôt. Platí 1 ≤ N ≤ 100 000.
Nasleduje N nezáporných celých čísel a1 až aN, udávajúcich (v neznámych jednotkách) namerané teploty v poradí zdola nahor. Môžete predpokladať, že každé z týchto čísel sa zmestí do 32-bitovej signed premennej.
Vypíšte jeden riadok a v ňom jedno celé číslo: počet dvojíc (i,j) takých, že i<j a aj>k*ai.
input
6 4 7 22 21 20 32 33 30 17 |
output4 |
Teploty 22, 21 a 20 sa správajú podľa očakávania. Nameraná hodnota 32 tvorí teplotnú inverziu s hodnotami 20 a 21. 22*(6/4)=33>32, preto dvojicu teplôt (22,32) za inverziu nepovažujeme, môže byť spôsobená chybou merania. Tá istá úvaha platí pre teplotu 33, opäť dostaneme dve inverzie. Teplota 30 žiadne platné inverzie netvorí a teplota 17 už tobôž nie.