Background

luanmenglei has a glorious present: all the girls in his class call him Yi-jiang.

But who would have thought that luanmenglei has a sad past: his five-year-old younger brother used to call him Big Brother Puppy.

Problem Description

All parameters below are integers by default.

As a game developer (of 7k7k mini-games), you designed the following game (so crude that it is not even as good as Big Brother Puppy’s kindergarten graduation project). It has two elements:

1. An enemy creature with health $m$.
2. The protagonist’s weapon, which has $n$ levels. The damage of level $i$ is $i \times p$.

The game balance needs to be planned in advance, so you also have a sequence $\{a_n\}$, defined as follows:

• $a_i$ means the enemy creature will die after being hit exactly $a_i$ times by the level $i$ weapon.

Unfortunately, you forgot what $p$ exactly is, so you need to find the number of all possible values of $p$.

If there can be infinitely many values of $p$, output xiaogougege.

Input Format

The first line contains two positive integers $n, m$.

The second line contains $n$ positive integers, representing the sequence $\{a_n\}$.

Output Format

Output one line containing one integer, the number of possible values of $p$, or the string xiaogougege. Its meaning is described in the statement.

3 3
3 2 1

1

Hint

Sample 1 Explanation

When the weapon is level $1$, analysis shows that $p$ must satisfy $1 \leq p < \frac{3}{2}$.
When the weapon is level $2$, analysis shows that $p$ must satisfy $\frac{3}{4} \leq p < \frac{3}{2}$.
When the weapon is level $3$, analysis shows that $p$ must satisfy $1 \leq p$.

Also, $p$ is an integer. Therefore, only $p = 1$ satisfies the conditions in the statement.

Sample 2

See game/game2.in and game/game2.out in the additional files.

This sample meets the constraints of test points $13 \sim 20$.

Constraints and Hints

For all testdata, it is guaranteed that $1 \leq n \leq 10^5$ and $1 \leq a_i, m \leq 10^9$.

The detailed constraints for each test point are shown in the table below:

Note that the specific generator code for the purely random testdata is as follows:

#include <bits/stdc++.h>
using namespace std;

int n, m, w;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  assert(l <= r);
  return uniform_int_distribution<>(l, r)(rng);
} 

int main() {
  scanf("%d%d%d", &n, &m, &w);
  printf("%d %d\n", n, m);
  for (int i = 1; i <= n; i ++) printf("%d%c", rand(1, w), " \n"[i == n]);
  return 0;
}

Simply put, for given $n, m, w (w \leq 10^9)$, the generator randomly generates $n$ numbers in the range $[1, w]$ as $\{a_n\}$.

Translated by ChatGPT 5