Description

Tianyi has decided on $n$ pieces of material, and they will be written in order in the essay. The theme feature value of the $i$-th piece of material is $a_i$.

However, Tianyi found that her masterpiece is far too long, so she wants to split them into exactly $k$ chapters. Each chapter contains a contiguous and non-empty segment of materials. Suppose the $i$-th chapter contains materials $[l_i,r_i]$. Tianyi will choose the material with the largest theme feature value to refine the idea, obtaining the theme value $b_i$ of this chapter, satisfying $b_i=\max\limits_{i\in[l_i,r_i]}\{a_i\}$.

Finally, the conciseness of the whole essay is the greatest common divisor of the theme values of all chapters, i.e., $\gcd\limits_{i\in[1,k]}\{b_i\}$.

Tianyi of course wants to maximize the conciseness of the essay. What is the maximum possible value of the conciseness?

Simplified statement

Given a sequence $a$ of length $n$, you must split it into exactly $k$ contiguous and non-empty segments. Define the theme value of the $i$-th segment as the maximum of all elements in that segment, denoted by $b_i$. You need to maximize $\gcd\limits_{i\in[1,k]}\{b_i\}$ and output this maximum value.

Input Format

The first line contains two integers $n,k$, representing the length of the materials and the number of chapters to split into.

The second line contains $n$ integers, representing the theme feature value of each piece of material.

Output Format

Output one integer in a single line, representing the answer.

5 3
1 3 2 9 6

3

5 2
10 2 5 5 5

5

Hint

Sample explanation 1

There may be multiple optimal ways to split the materials. Here is one optimal split: divide these $5$ materials into $3$ chapters: $[1,3],[2,9],[6]$. Then $b_1=3,b_2=9,b_3=6$, and the maximum conciseness is $\gcd(3,9,6)=3$.

Constraints and notes

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le k\le n\le 10^5$, $1\le a_i\le 10^{6}$.

Translated by ChatGPT 5