F. Pens And Days Of Week

Stepan 有 #cf_span[n] 支笔。每天他都会使用它们，第 #cf_span[i] 天他使用第 #cf_span[i] 支笔。第 #cf_span[(n + 1)] 天他又使用第 #cf_span[1] 支笔，第 #cf_span[(n + 2)] 天使用第 #cf_span[2] 支笔，依此类推。 在每个工作日（从周一到周六，包含两端），Stepan 会消耗他当天所用笔 exactly #cf_span[1] 毫升墨水。周日是 Stepan 的休息日，他不会消耗当天所用笔的墨水。 Stepan 知道每支笔当前的墨水量。现在是 *周一早晨*，Stepan 将在今天使用 *第 #cf_span[1] 支笔*。你的任务是确定，在按照上述规则使用笔的情况下，哪一支笔会最先耗尽墨水（即墨水完全用完）。 第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50 000]）——Stepan 拥有的笔的数量。 第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示第 #cf_span[i] 支笔当前的墨水量（单位：毫升）。 请输出在按照上述规则使用笔的情况下，最先耗尽墨水的笔的编号（即墨水完全用完的那支笔）。笔的编号按照输入顺序从 1 开始编号。 注意：答案总是唯一的，因为不可能有两支笔同时耗尽墨水。 在第一个测试用例中，Stepan 使用笔的墨水情况如下： 因此，最先没有墨水的笔是第 #cf_span[2] 支笔。 ## Input 第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50 000]）——Stepan 拥有的笔的数量。第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示第 #cf_span[i] 支笔当前的墨水量（单位：毫升）。 ## Output 请输出在按照上述规则使用笔的情况下，最先耗尽墨水的笔的编号（即墨水完全用完的那支笔）。笔的编号按照输入顺序从 1 开始编号。注意：答案总是唯一的，因为不可能有两支笔同时耗尽墨水。 [samples] ## Note 在第一个测试用例中，Stepan 使用笔的墨水情况如下： - 第 #cf_span[1] 天（周一）：使用第 #cf_span[1] 支笔，之后该笔剩余 #cf_span[2] 毫升墨水； - 第 #cf_span[2] 天（周二）：使用第 #cf_span[2] 支笔，之后该笔剩余 #cf_span[2] 毫升墨水； - 第 #cf_span[3] 天（周三）：使用第 #cf_span[3] 支笔，之后该笔剩余 #cf_span[2] 毫升墨水； - 第 #cf_span[4] 天（周四）：使用第 #cf_span[1] 支笔，之后该笔剩余 #cf_span[1] 毫升墨水； - 第 #cf_span[5] 天（周五）：使用第 #cf_span[2] 支笔，之后该笔剩余 #cf_span[1] 毫升墨水； - 第 #cf_span[6] 天（周六）：使用第 #cf_span[3] 支笔，之后该笔剩余 #cf_span[1] 毫升墨水； - 第 #cf_span[7] 天（周日）：使用第 #cf_span[1] 支笔，但这是休息日，因此不消耗墨水； - 第 #cf_span[8] 天（周一）：使用第 #cf_span[2] 支笔，之后该笔墨水耗尽。 因此，最先没有墨水的笔是第 #cf_span[2] 支笔。

Let $ n $ be the number of pens. Let $ a = [a_1, a_2, \dots, a_n] $ be the initial ink volumes (in milliliters) of the pens, where $ a_i $ is the ink volume in pen $ i $. Stepan uses pens in a cyclic order: on day $ d $, he uses pen $ ((d-1) \bmod n) + 1 $. He uses ink **only on working days**: Monday through Saturday (6 days per week); **no ink is used on Sunday**. The cycle of days repeats every 7 days, but only 6 of them are working. Thus, every 7-day cycle corresponds to 6 ink usages. On day $ d $, pen $ p = ((d-1) \bmod n) + 1 $ is used, and if $ d \not\equiv 0 \pmod{7} $, then 1 mL of ink is consumed from pen $ p $. We are told that day 1 is **Monday**, so day $ d $ is a working day if and only if $ d \bmod 7 \neq 0 $. We wish to find the **smallest index $ i \in \{1, 2, \dots, n\} $** such that pen $ i $ runs out of ink **before** any other pen. That is, find the pen $ i $ for which the **first day** $ d $ such that the total ink consumed from pen $ i $ reaches $ a_i $ is **minimal** among all pens. --- ### Formal Problem: Define $ c_i(k) $: number of times pen $ i $ is used during the first $ k $ days. Since pens are used cyclically every $ n $ days, and only working days (non-Sunday) consume ink: Let $ f(d) = \sum_{j=1}^d \mathbf{1}_{j \bmod 7 \ne 0} $: total working days up to day $ d $. Let $ p(j) = ((j-1) \bmod n) + 1 $: pen used on day $ j $. Then, the total ink consumed from pen $ i $ by day $ d $ is: $$ I_i(d) = \sum_{j=1}^d \mathbf{1}_{p(j) = i} \cdot \mathbf{1}_{j \bmod 7 \ne 0} $$ We seek the smallest $ i \in \{1, 2, \dots, n\} $ such that: $$ \min \left\{ d \in \mathbb{N} : I_i(d) = a_i \right\} < \min \left\{ d \in \mathbb{N} : I_j(d) = a_j \right\} \quad \forall j \ne i $$ --- ### Alternative Efficient Approach: Let $ T $ be the number of full 7-day cycles (weeks) that have passed. In each week, there are 6 working days. In each week, each pen is used $ \left\lfloor \frac{6}{n} \right\rfloor $ or $ \left\lceil \frac{6}{n} \right\rceil $ times, depending on alignment. But since the usage pattern is periodic with period $ \mathrm{lcm}(n, 7) $, and $ n \leq 50000 $, we can instead compute for each pen $ i $, the **minimum number of working days** $ D_i $ required to consume $ a_i $ mL of ink from pen $ i $. Since pen $ i $ is used every $ n $ days, the days it is used are: $$ d \equiv i \pmod{n}, \quad d \in \mathbb{N} $$ Among these, we only count those where $ d \not\equiv 0 \pmod{7} $. We want the smallest $ D_i $ such that among the first $ D_i $ working days, pen $ i $ has been used $ a_i $ times. But since the pattern of pen usage and working days is periodic with period $ L = \mathrm{lcm}(n, 7) $, we can precompute how many times pen $ i $ is used in one full period $ L $, and how many of those usages occur on working days. Let $ c_i = $ number of times pen $ i $ is used on working days in one period $ L = \mathrm{lcm}(n, 7) $. Then, the number of full periods needed to consume $ a_i $ mL is $ q_i = \left\lfloor \frac{a_i - 1}{c_i} \right\rfloor $, and the remaining usage is $ r_i = a_i - q_i \cdot c_i $. Then we simulate within one period to find the smallest day $ d \leq L $ such that pen $ i $ has been used $ r_i $ times on working days. Then total days until pen $ i $ runs out: $ d_i = q_i \cdot L + d_{\text{remaining}} $ We compute $ d_i $ for all $ i $, and return the $ i $ with **minimal** $ d_i $. --- ### Final Formal Statement: Let $ L = \mathrm{lcm}(n, 7) $ For each pen $ i \in \{1, 2, \dots, n\} $: - Let $ S_i = \{ d \in [1, L] : d \equiv i \pmod{n} \text{ and } d \not\equiv 0 \pmod{7} \} $ - Let $ c_i = |S_i| $: number of times pen $ i $ is used on working days in one full cycle of $ L $ days. - Let $ q_i = \left\lfloor \frac{a_i - 1}{c_i} \right\rfloor $ - Let $ r_i = a_i - q_i \cdot c_i $ - Find the smallest $ d_i' \in [1, L] $ such that among the first $ d_i' $ days, pen $ i $ has been used on working days exactly $ r_i $ times. - Then total days until pen $ i $ runs out: $ D_i = q_i \cdot L + d_i' $ Return the index $ i \in \{1, 2, \dots, n\} $ that minimizes $ D_i $. --- **Output:** $ \boxed{i} $, where $ i = \arg\min_{1 \le j \le n} D_j $