P7244 Chapter Partitioning

  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.

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.

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 one integer in a single line, representing the answer.

#### 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}$. | Subtask | Points | $n$ | $k$ | $a_i$ | | :----: | :--: | :----------------: | :--: | :----------------: | | 1 | 5 | $\le 5$ | / | / | | 2 | 10 | $\le 10^2$ | / | / | | 3 | 10 | / | $2$ | / | | 4 | 15 | / | $3$ | / | | 5 | 20 | $\le 3\times 10^3$ | / | / | | 6 | 10 | / | / | $\le 2\times 10^2$ | | 7 | 30 | / | / | / | Translated by ChatGPT 5