P7244 章节划分

  作文周，顾名思义，一天写一篇，高产似那啥。   小灰毛的作文被老师无数次公开处刑，昨天自己的奶奶变成了别人作文里的外婆，今天憋出来的小面变成了明天别人的酸辣粉。素材一用，就报废了啊 qwq。   于是，不甘心的小灰毛决定加倍高产。

天依决定了 $n$ 个素材，它们将**依次**在作文中被叙写。其中，第 $i$ 个素材的立意特征值是 $a_i$。 但天依发现她构思的大作实在是太长啦，所以她想把它们划分为**恰好 $k$ 个**章节，每个章节包含一段**连续且非空的**素材。假设第 $i$ 个章节包含素材 $[l_i,r_i]$，天依将选取立意特征值最大的素材来升华，得到该章节的立意值 $b_i$，满足 $b_i=\max\limits_{i\in[l_i,r_i]}\{a_i\}$。 最后，整篇作文的凝练度为每个章节立意值的**最大公约数**，即 $\gcd\limits_{i\in[1,k]}\{b_i\}$。 天依当然希望**最大化**作文的凝练度，那么凝练度的最大值是多少呢？ --- #### 简化题意 有一个长度为 $n$ 的序列 $a$。要求将这个序列**恰好**分成**连续且非空**的 $k$ 段，并定义第 $i$ 段的立意值为该段的所有元素的最大值，记为 $b_i$。要求最大化 $\gcd\limits_{i\in[1,k]}\{b_i\}$ 并输出这个最大值。

无

无

#### 样例解释 1 最优的素材划分可能有多种，这里给出一种最优的素材划分，将这 $5$ 个素材分成 $3$ 个章节：$[1,3],[2,9],[6]$，可以得出 $b_1=3,b_2=9,b_3=6$，凝练度的最大值为 $\gcd(3,9,6)=3$。 ------------ #### 数据规模与约定 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\le k\le n\le 10^5$，$1\le a_i\le 10^{6}$。 | 子任务 | 分值 | $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 | / | / | / |