{"problem":{"name":"H. A lot of work","description":{"content":"— And Prince — what games does he play? — Princess looked at Dragon thoughtfully. — Prince... He has so many different affairs all the time, he has no time for games, — Dragon thought for a moment an","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070H"},"statements":[{"statement_type":"Markdown","content":"— And Prince — what games does he play? — Princess looked at Dragon thoughtfully.\n\n— Prince... He has so many different affairs all the time, he has no time for games, — Dragon thought for a moment and added, — Perhaps, that he is busy all the time is a reason why he doesn't want to play games...\n\nPrince does his best to work as effectively as possible. So, some time ago Prince observed, that if he performs the same job during more than one unit of time, his work efficiency decreases conspicuously. For this reason he tries to do different jobs at any two consecutive units of time now.\n\nPrince reports about all the work he does. After doing some kind of job during one unit of time, he paints over a cell on a strip of paper with a marker. One day Dragon took an interest what do all those colored squares mean. Prince clarified that every job corresponds to a color. Unfortunately, the number of markers is limited, so Prince can use the same color for different jobs. Of course, in this case the next job starts after the end of the previous job.\n\nPrince boasted of his methods, and mentioned that he uses, among the other things, a forgetting parameter. The _forgetting parameter_ is an integer k, a maximum allowable distance between two cells of the same color, if these cells are associated with the same job. It is clear, that it is not guaranteed that cells are associated with the same job if distance between cells is not greater than k and they have the same color. But it is guaranteed that every two cells are associated with different jobs if distance between them is greater than k and they have the same color.\n\nDragon interests what minimum number of different jobs Prince could have done for the last time. Your task is to compute it by a given colored strip and a value of k. For the sake of simplicity we use numbers instead of colors.\n\nThe first line contains integer n (1 ≤ n ≤ 105) — the number of colored cells. \n\nThe second line contains sequence of numbers c1, c2, ..., cn (1 ≤ cj ≤ 105) — the description of colored cells. The same numbers correspond to the same colors and vice versa.\n\nThe third line contains integer q (1 ≤ q ≤ 105) — the number of queries.\n\nThe fourth line contains integers k1, k2, ..., kq (1 ≤ k ≤ n) — the values of forgetting parameter, for every of which you should compute minimum possible number of jobs that Prince could have done during n units of time.\n\nPrint q integers dj (j = 1, 2, ..., q) in the first line. Number dj is the minimum possible number of jobs that Prince could have done for jth value of forgetting parameter.\n\n## Input\n\nThe first line contains integer n (1 ≤ n ≤ 105) — the number of colored cells. The second line contains sequence of numbers c1, c2, ..., cn (1 ≤ cj ≤ 105) — the description of colored cells. The same numbers correspond to the same colors and vice versa.The third line contains integer q (1 ≤ q ≤ 105) — the number of queries.The fourth line contains integers k1, k2, ..., kq (1 ≤ k ≤ n) — the values of forgetting parameter, for every of which you should compute minimum possible number of jobs that Prince could have done during n units of time.\n\n## Output\n\nPrint q integers dj (j = 1, 2, ..., q) in the first line. Number dj is the minimum possible number of jobs that Prince could have done for jth value of forgetting parameter.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence.  \nLet $ C = (c_1, c_2, \\dots, c_n) $ be a sequence of colors, where $ c_i \\in \\mathbb{Z}^+ $ and $ 1 \\leq c_i \\leq 10^5 $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ K = (k_1, k_2, \\dots, k_q) $ be a sequence of forgetting parameters, where $ k_j \\in \\mathbb{Z}^+ $ and $ 1 \\leq k_j \\leq n $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq c_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq q \\leq 10^5 $  \n4. $ 1 \\leq k_j \\leq n $ for all $ j \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, compute the minimum number of distinct jobs $ d_j $ consistent with the following rule:  \n> If two positions $ i < i' $ have the same color $ c_i = c_{i'} $ and $ i' - i > k_j $, then they must correspond to **different jobs**.  \n> If $ i' - i \\leq k_j $, they *may* correspond to the same job (but are not required to).\n\nThe goal is to assign jobs (i.e., label each position with a job ID) such that:  \n- Positions with the same color and distance $ > k_j $ receive **different** job IDs.  \n- The total number of distinct job IDs is minimized.\n\nFormally, define an assignment $ f: \\{1, \\dots, n\\} \\to \\mathbb{Z}^+ $, where $ f(i) $ is the job ID assigned to position $ i $.  \nMinimize $ \\left| \\{ f(i) \\mid i \\in \\{1, \\dots, n\\} \\} \\right| $, subject to:  \n$$\n\\forall i < i', \\quad \\text{if } c_i = c_{i'} \\text{ and } i' - i > k_j, \\text{ then } f(i) \\ne f(i')\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}