{"problem":{"name":"F. Pens And Days Of Week","description":{"content":"Stepan has _n_ pens. Every day he uses them, and on the _i_\\-th day he uses the pen number _i_. On the (_n_ + 1)\\-th day again he uses the pen number 1, on the (_n_ + 2)\\-th — he uses the pen number 2","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF795F"},"statements":[{"statement_type":"Markdown","content":"Stepan has _n_ pens. Every day he uses them, and on the _i_\\-th day he uses the pen number _i_. On the (_n_ + 1)\\-th day again he uses the pen number 1, on the (_n_ + 2)\\-th — he uses the pen number 2 and so on.\n\nOn every working day (from Monday to Saturday, inclusive) Stepan spends exactly 1 milliliter of ink of the pen he uses that day. On Sunday Stepan has a day of rest, he does not stend the ink of the pen he uses that day.\n\nStepan knows the current volume of ink in each of his pens. Now it's the **Monday morning** and Stepan is going to use the pen **number 1** today. Your task is to determine which pen will run out of ink before all the rest (that is, there will be no ink left in it), if Stepan will use the pens according to the conditions described above.\n\n## Input\n\nThe first line contains the integer _n_ (1 ≤ _n_ ≤ 50 000) — the number of pens Stepan has.\n\nThe second line contains the sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is equal to the number of milliliters of ink which the pen number _i_ currently has.\n\n## Output\n\nPrint the index of the pen which will run out of ink before all (it means that there will be no ink left in it), if Stepan will use pens according to the conditions described above.\n\nPens are numbered in the order they are given in input data. The numeration begins from one.\n\nNote that the answer is always unambiguous, since several pens can not end at the same time.\n\n[samples]\n\n## Note\n\nIn the first test Stepan uses ink of pens as follows:\n\n1.  on the day number 1 (Monday) Stepan will use the pen number 1, after that there will be 2 milliliters of ink in it;\n2.  on the day number 2 (Tuesday) Stepan will use the pen number 2, after that there will be 2 milliliters of ink in it;\n3.  on the day number 3 (Wednesday) Stepan will use the pen number 3, after that there will be 2 milliliters of ink in it;\n4.  on the day number 4 (Thursday) Stepan will use the pen number 1, after that there will be 1 milliliters of ink in it;\n5.  on the day number 5 (Friday) Stepan will use the pen number 2, after that there will be 1 milliliters of ink in it;\n6.  on the day number 6 (Saturday) Stepan will use the pen number 3, after that there will be 1 milliliters of ink in it;\n7.  on the day number 7 (Sunday) Stepan will use the pen number 1, but it is a day of rest so he will not waste ink of this pen in it;\n8.  on the day number 8 (Monday) Stepan will use the pen number 2, after that this pen will run out of ink.\n\nSo, the first pen which will not have ink is the pen number 2.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Stepan 有 #cf_span[n] 支笔。每天他都会使用它们，第 #cf_span[i] 天他使用第 #cf_span[i] 支笔。第 #cf_span[(n + 1)] 天他又使用第 #cf_span[1] 支笔，第 #cf_span[(n + 2)] 天使用第 #cf_span[2] 支笔，依此类推。\n\n在每个工作日（从周一到周六，包含两端），Stepan 会消耗他当天所用笔 exactly #cf_span[1] 毫升墨水。周日是 Stepan 的休息日，他不会消耗当天所用笔的墨水。\n\nStepan 知道每支笔当前的墨水量。现在是 *周一早晨*，Stepan 将在今天使用 *第 #cf_span[1] 支笔*。你的任务是确定，在按照上述规则使用笔的情况下，哪一支笔会最先耗尽墨水（即墨水完全用完）。\n\n第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50 000]）——Stepan 拥有的笔的数量。\n\n第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示第 #cf_span[i] 支笔当前的墨水量（单位：毫升）。\n\n请输出在按照上述规则使用笔的情况下，最先耗尽墨水的笔的编号（即墨水完全用完的那支笔）。笔的编号按照输入顺序从 1 开始编号。\n\n注意：答案总是唯一的，因为不可能有两支笔同时耗尽墨水。\n\n在第一个测试用例中，Stepan 使用笔的墨水情况如下：\n\n因此，最先没有墨水的笔是第 #cf_span[2] 支笔。\n\n## Input\n\n第一行包含整数 #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] 支笔当前的墨水量（单位：毫升）。\n\n## Output\n\n请输出在按照上述规则使用笔的情况下，最先耗尽墨水的笔的编号（即墨水完全用完的那支笔）。笔的编号按照输入顺序从 1 开始编号。注意：答案总是唯一的，因为不可能有两支笔同时耗尽墨水。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，Stepan 使用笔的墨水情况如下：\n\n- 第 #cf_span[1] 天（周一）：使用第 #cf_span[1] 支笔，之后该笔剩余 #cf_span[2] 毫升墨水；\n- 第 #cf_span[2] 天（周二）：使用第 #cf_span[2] 支笔，之后该笔剩余 #cf_span[2] 毫升墨水；\n- 第 #cf_span[3] 天（周三）：使用第 #cf_span[3] 支笔，之后该笔剩余 #cf_span[2] 毫升墨水；\n- 第 #cf_span[4] 天（周四）：使用第 #cf_span[1] 支笔，之后该笔剩余 #cf_span[1] 毫升墨水；\n- 第 #cf_span[5] 天（周五）：使用第 #cf_span[2] 支笔，之后该笔剩余 #cf_span[1] 毫升墨水；\n- 第 #cf_span[6] 天（周六）：使用第 #cf_span[3] 支笔，之后该笔剩余 #cf_span[1] 毫升墨水；\n- 第 #cf_span[7] 天（周日）：使用第 #cf_span[1] 支笔，但这是休息日，因此不消耗墨水；\n- 第 #cf_span[8] 天（周一）：使用第 #cf_span[2] 支笔，之后该笔墨水耗尽。\n\n因此，最先没有墨水的笔是第 #cf_span[2] 支笔。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of pens.  \nLet $ 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 $.\n\nStepan uses pens in a cyclic order: on day $ d $, he uses pen $ ((d-1) \\bmod n) + 1 $.  \nHe uses ink **only on working days**: Monday through Saturday (6 days per week); **no ink is used on Sunday**.\n\nThe cycle of days repeats every 7 days, but only 6 of them are working.  \nThus, every 7-day cycle corresponds to 6 ink usages.\n\nOn 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 $.\n\nWe are told that day 1 is **Monday**, so day $ d $ is a working day if and only if $ d \\bmod 7 \\neq 0 $.\n\nWe wish to find the **smallest index $ i \\in \\{1, 2, \\dots, n\\} $** such that pen $ i $ runs out of ink **before** any other pen.\n\nThat 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.\n\n---\n\n### Formal Problem:\n\nDefine $ c_i(k) $: number of times pen $ i $ is used during the first $ k $ days.\n\nSince pens are used cyclically every $ n $ days, and only working days (non-Sunday) consume ink:\n\nLet $ f(d) = \\sum_{j=1}^d \\mathbf{1}_{j \\bmod 7 \\ne 0} $: total working days up to day $ d $.\n\nLet $ p(j) = ((j-1) \\bmod n) + 1 $: pen used on day $ j $.\n\nThen, the total ink consumed from pen $ i $ by day $ d $ is:\n\n$$\nI_i(d) = \\sum_{j=1}^d \\mathbf{1}_{p(j) = i} \\cdot \\mathbf{1}_{j \\bmod 7 \\ne 0}\n$$\n\nWe seek the smallest $ i \\in \\{1, 2, \\dots, n\\} $ such that:\n\n$$\n\\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\n$$\n\n---\n\n### Alternative Efficient Approach:\n\nLet $ T $ be the number of full 7-day cycles (weeks) that have passed.  \nIn each week, there are 6 working days.  \nIn 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.\n\nBut 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 $.\n\nSince pen $ i $ is used every $ n $ days, the days it is used are:\n\n$$\nd \\equiv i \\pmod{n}, \\quad d \\in \\mathbb{N}\n$$\n\nAmong these, we only count those where $ d \\not\\equiv 0 \\pmod{7} $.\n\nWe want the smallest $ D_i $ such that among the first $ D_i $ working days, pen $ i $ has been used $ a_i $ times.\n\nBut 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.\n\nLet $ c_i = $ number of times pen $ i $ is used on working days in one period $ L = \\mathrm{lcm}(n, 7) $.\n\nThen, 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 $.\n\nThen 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.\n\nThen total days until pen $ i $ runs out: $ d_i = q_i \\cdot L + d_{\\text{remaining}} $\n\nWe compute $ d_i $ for all $ i $, and return the $ i $ with **minimal** $ d_i $.\n\n---\n\n### Final Formal Statement:\n\nLet $ L = \\mathrm{lcm}(n, 7) $\n\nFor each pen $ i \\in \\{1, 2, \\dots, n\\} $:\n\n- Let $ S_i = \\{ d \\in [1, L] : d \\equiv i \\pmod{n} \\text{ and } d \\not\\equiv 0 \\pmod{7} \\} $\n- Let $ c_i = |S_i| $: number of times pen $ i $ is used on working days in one full cycle of $ L $ days.\n- Let $ q_i = \\left\\lfloor \\frac{a_i - 1}{c_i} \\right\\rfloor $\n- Let $ r_i = a_i - q_i \\cdot c_i $\n- 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.\n- Then total days until pen $ i $ runs out: $ D_i = q_i \\cdot L + d_i' $\n\nReturn the index $ i \\in \\{1, 2, \\dots, n\\} $ that minimizes $ D_i $.\n\n---\n\n**Output:** $ \\boxed{i} $, where $ i = \\arg\\min_{1 \\le j \\le n} D_j $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF795F","tags":["brute force","math","number theory"],"sample_group":[["3\n3 3 3","2"],["5\n5 4 5 4 4","5"]],"created_at":"2026-03-03 11:00:39"}}