Farmer John a aligné $N$ vaches pour mesurer leur taille, $1 \le N \le 100,000$. La vache $i$ mesure $H_{i}$ nanomètres, $1 \le H_{i} \le 1,000,000,000$ : FJ croit aux mesures précises ! Il veut photographier une sous-séquence contiguë pour le concours de photographie bovine à la foire du comté.
Une règle étrange impose à toute photo que la taille médiane du groupe soit au moins un seuil $X$, $1 \le X \le 1,000,000,000$, pour être recevable.
La médiane d'un tableau $A[0...K]$ est ici $A[\mathrm{ceiling}(K/2)]$ après tri de $A$. $\mathrm{ceiling}(K/2)$ arrondit $K/2$ à l'entier supérieur (ou conserve $K/2$ si $K/2$ est déjà entier). Ainsi $\{7,3,2,6\}$ a pour médiane 6, et $\{5,4,8\}$ a pour médiane 5.
Comptez les sous-séquences contiguës différentes que FJ pourrait présenter.
Entrée
- Ligne 1 : deux entiers $N$ et $X$, séparés par une espace.
- Lignes 2..$N$+1 : la ligne $i+1$ contient l'entier $H_{i}$.
Sortie
- Ligne 1 : le nombre de sous-séquences de médiane au moins $X$. Il peut dépasser un entier de 32 bits.
Exemples
Entrée 1
4 6 10 5 6 2
Sortie 1
7
Remarque
Les quatre tailles sont $10,5,6,2$. On cherche les sous-séquences contiguës de médiane au moins 6.
Il y en a 10 possibles, dont seulement 7 de médiane au moins 6 : $\{10\}$, $\{6\}$, $\{10,5\}$, $\{5,6\}$, $\{6,2\}$, $\{10,5,6\}$, $\{10,5,6,2\}$.
Auteur du problème : Brian Dean