26782번 - Notowania akcji 다국어

Firma Bajtex N dni temu wypuściła swoje akcje na bajtockiej giełdzie. Firma ta zastanawia się teraz jak przekonać nowych akcjonariuszy do zainwestowania w swoje akcje. Poza faktem, że akcje przynoszą zyski, firma chciałaby pokazać potencjalnym zainteresowanym, że ich akcje ciągle idą w górę. Aby to zrobić, zdecydowali się wybrać K-fragment, czyli ciąg kolejnych K dni, w którym cena akcji wyłącznie rosła i pokazać te dane potencjalnym zainteresowanym. Teraz zastanawiają sie, ile takich K-fragmentów było dla różnych wartości K.

Dla przykładu, rozważmy następujące kursy akcji firmy Bajtex:

Jeżeli chcielibyśmy wybrać jedynie dwa dni (czyli jeśli rozważamy 2-fragmenty), to możemy to zrobić na pięć sposobów: (2, 3), (3, 4), (4, 5), (7, 8), (8, 9). Zauważ, że nie możemy wybrać dni (5, 6), jako że cena akcji nie wzrosła, a jedynie się utrzymała. Z kolei, jeżeli chcielibyśmy wybrać trzy dni (czyli jeśli rozważamy 3-fragmenty), to możemy to zrobić na trzy sposoby: (2, 3, 4), (3, 4, 5) oraz (7, 8, 9). Nie możemy wybrać dni (1, 2, 3), ponieważ zanotowaliśmy spadek pomiędzy pierwszym a drugim dniem.

Twoim zadaniem będzie dla różnych K obliczyć ile mamy K-fragmentów w danym ciągu.

Napisz program, który wczyta notowania akcji firmy Bajtex oraz zapytania o serie wzrostów, dla każdego zapytania K_i wyznaczy liczbę K_i-fragmentów (czyli spójnych ciągów notowań akcji o długości K_i, w których akcje firmy były ściśle rosnące) i wypisze wyniki na standardowe wyjście.

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 500 000), określająca liczbę dni przez które firma Bajtex była na giełdzie. W drugim wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych A_i (0 ≤ A_i ≤ 10⁹), pooddzielanych pojedynczymi odstępami. Są to notowania akcji Bajtex w kolejnych dniach. W trzecim wierszu wejścia znajduje się jedna liczba naturalna Q (1 ≤ Q ≤ 500 000), określająca liczbę zapytań. W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z jednej liczby naturalnej K_i (1 ≤ K_i ≤ N), określającej zapytanie o liczbę Ki-fragmentów w ciągu notowań akcji.

Twój program powinien wypisać na wyjście ciąg Q liczb całkowitych w osobnych wierszach. i-ta spośród nich powinna określać liczbę K_i-fragmentów.