题目描述
现在有长度为 nnn 的数组 aaa，式子 SSS 定义为 S=a1÷a2÷a3...÷anS=a_1\div a_2\div a_3...\div a_nS=a1÷a2÷a3...÷an，最多对数组 aaa 进行 ttt 次循环右移操作。
请问，进行第几次操作时使得 SSS 最大？若存在多种答案，请输出最小值。
循环右移：一次操作使数组从 a1,a2,a3,...,ana_1,a_2,a_3,...,a_na1,a2,a3,...,an 形式转换为 an,a1,a2,...,an−1a_n,a_1,a_2,...,a_{n-1}an,a1,a2,...,an−1 形式。
输入
输入包含两行.
第一行一个正整数 n,tn,tn,t (1≤n≤2×105,0≤t≤109)(1\leq n\leq 2\times10^5,0\leq t\leq 10^9)(1≤n≤2×105,0≤t≤109) 表示数组 aaa 的长度和最多的操作次数。
第二行 nnn 个正整数 aia_iai (1≤ai≤109)(1\leq a_i \leq10^9)(1≤ai≤109) 表示数组 aaa 的元素。
第一行一个正整数 n,tn,tn,t (1≤n≤2×105,0≤t≤109)(1\leq n\leq 2\times10^5,0\leq t\leq 10^9)(1≤n≤2×105,0≤t≤109) 表示数组 aaa 的长度和最多的操作次数。
第二行 nnn 个正整数 aia_iai (1≤ai≤109)(1\leq a_i \leq10^9)(1≤ai≤109) 表示数组 aaa 的元素。
输出
输出包含一行一个整数，表示使得 SS 最大的最小操作次数。 样例输入 Copy
5 10
5 3 4 1 2
样例输出 Copy
0
提示
操作0次时使得 S=5÷3÷4÷1÷2S=5÷3÷4÷1÷2 最大
÷ 是正常除法，不是向上取整或向下取整。