Background

  During essay week, as the name suggests, you write one essay a day, producing a lot of work.

  Xiao Huimao’s essays have been “publicly executed” by the teacher countless times. Yesterday, her own grandma turned into someone else’s “maternal grandma” in another essay; today, the noodles she finally managed to write about became someone else’s hot and sour rice noodles tomorrow. Once you use your material, it is basically ruined, qwq.

  So, unwilling to give up, Xiao Huimao decided to be even more productive.

Problem 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