MAX-=min

AtCoder

IDarc105_b

Time2000ms

Memory256MB

Difficulty—

Snuke had $N$ cards numbered $1$ through $N$. Each card has an integer written on it; written on Card $i$ is $a_i$. Snuke did the following procedure: 1. Let $X$ and $x$ be the maximum and minimum values written on Snuke's cards, respectively. 2. If $X = x$, terminate the procedure. Otherwise, replace each card on which $X$ is written with a card on which $X-x$ is written, then go back to step 1. Under the constraints in this problem, it can be proved that the procedure will eventually terminate. Find the number written on all of Snuke's cards after the procedure. ## Constraints * All values in input are integers. * $1 \leq N \leq 10^{5}$ * $1 \leq a_i \leq 10^9$ ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $a_2$ $\cdots$ $a_N$ [samples]

Samples

Input #1

3
2 6 6

Output #1

2

*   At the beginning of the procedure, the numbers written on Snuke's cards are $(2,6,6)$.
    *   Since $x=2$ and $X=6$, he replaces each card on which $6$ is written with a card on which $4$ is written.
*   Now, the numbers written on Snuke's cards are $(2,4,4)$.
    *   Since $x=2$ and $X=4$, he replaces each card on which $4$ is written with a card on which $2$ is written.
*   Now, the numbers written on Snuke's cards are $(2,2,2)$.
    *   Since $x=2$ and $X=2$, he terminates the procedure.

Input #2

15
546 3192 1932 630 2100 4116 3906 3234 1302 1806 3528 3780 252 1008 588

Output #2

API Response (JSON)

{
  "problem": {
    "name": "MAX-=min",
    "description": {
      "content": "Snuke had $N$ cards numbered $1$ through $N$. Each card has an integer written on it; written on Card $i$ is $a_i$. Snuke did the following procedure: 1.  Let $X$ and $x$ be the maximum and minimum v",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc105_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke had $N$ cards numbered $1$ through $N$. Each card has an integer written on it; written on Card $i$ is $a_i$.\nSnuke did the following procedure:\n\n1.  Let $X$ and $x$ be the maximum and minimum v...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments