English · Original
Chinese · Translation
Formal · Original
There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission.
Heidi has _n_ Jedi Knights standing in front of her, each one with a lightsaber of one of _m_ possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly _k_1 knights with lightsabers of the first color, _k_2 knights with lightsabers of the second color, ..., _k__m_ knights with lightsabers of the _m_\-th color.
However, since the last time, she has learned that it is not always possible to select such an interval. Therefore, she decided to ask some Jedi Knights to go on an indefinite unpaid vacation leave near certain pits on Tatooine, if you know what I mean. Help Heidi decide what is the minimum number of Jedi Knights that need to be let go before she is able to select the desired interval from the subsequence of remaining knights.
## Input
The first line of the input contains _n_ (1 ≤ _n_ ≤ 2·105) and _m_ (1 ≤ _m_ ≤ _n_). The second line contains _n_ integers in the range {1, 2, ..., _m_} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains _m_ integers _k_1, _k_2, ..., _k__m_ (with ) – the desired counts of Jedi Knights with lightsabers of each color from 1 to _m_.
## Output
Output one number: the minimum number of Jedi Knights that need to be removed from the sequence so that, in what remains, there is an interval with the prescribed counts of lightsaber colors. If this is not possible, output - 1.
[samples]
银河议会中动荡不安。数千个恒星系统已宣布意图脱离共和国。海迪大师需要挑选出前往全银河执行维和任务的绝地武士。众所周知，任何维和任务的成功都取决于参与任务的绝地武士光剑的颜色。
海迪面前有 #cf_span[n] 名绝地武士排成一列，每人持有一把颜色属于 #cf_span[m] 种可能颜色之一的光剑。她知道，为了使任务最有效，她需要选出一个连续的武士区间，使得其中恰好有 #cf_span[k1] 名武士的光剑为第一种颜色，#cf_span[k2] 名武士的光剑为第二种颜色，#cf_span[...]，#cf_span[km] 名武士的光剑为第 #cf_span[m] 种颜色。
然而，由于上次的经验，她发现并非总能找到这样的区间。因此，她决定让一些绝地武士去塔图因星的某些坑洞附近休无薪长假——你知道我说的是什么意思。请帮助海迪决定：在她能够从剩余武士的子序列中选出所需区间之前，最少需要让多少名绝地武士离开？
输入的第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) 和 #cf_span[m] (#cf_span[1 ≤ m ≤ n])。第二行包含 #cf_span[n] 个整数，范围为 #cf_span[{1, 2, ..., m}]，表示后续绝地武士光剑的颜色。第三行包含 #cf_span[m] 个整数 #cf_span[k1, k2, ..., km]（满足 ）——表示从颜色 #cf_span[1] 到 #cf_span[m] 所需的每种颜色的绝地武士数量。
输出一个数字：为使剩余序列中存在一个区间，其光剑颜色计数符合要求，最少需要移除的绝地武士数量。如果不可能实现，请输出 #cf_span[ - 1]。
## Input
输入的第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) 和 #cf_span[m] (#cf_span[1 ≤ m ≤ n])。第二行包含 #cf_span[n] 个整数，范围为 #cf_span[{1, 2, ..., m}]，表示后续绝地武士光剑的颜色。第三行包含 #cf_span[m] 个整数 #cf_span[k1, k2, ..., km]（满足 ）——表示从颜色 #cf_span[1] 到 #cf_span[m] 所需的每种颜色的绝地武士数量。
## Output
输出一个数字：为使剩余序列中存在一个区间，其光剑颜色计数符合要求，最少需要移除的绝地武士数量。如果不可能实现，请输出 #cf_span[ - 1]。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $, with $ 1 \leq m \leq n \leq 2 \cdot 10^5 $.
Let $ C = (c_1, c_2, \dots, c_n) $ be a sequence of integers, where $ c_i \in \{1, 2, \dots, m\} $, representing the lightsaber color of the $ i $-th Jedi Knight.
Let $ K = (k_1, k_2, \dots, k_m) \in \mathbb{Z}_{\geq 0}^m $ be the target frequency vector, where $ k_j $ is the required number of Jedi Knights with lightsaber color $ j $.
**Constraints**
1. $ \sum_{j=1}^m k_j \geq 1 $
2. For all $ j \in \{1, \dots, m\} $, $ k_j \leq \text{count of color } j \text{ in } C $
**Objective**
Find the minimum number of Jedi Knights to remove from $ C $ such that the remaining sequence contains a contiguous subarray (interval) in which, for each color $ j \in \{1, \dots, m\} $, exactly $ k_j $ Jedi Knights have lightsabers of color $ j $.
If no such subarray can be formed after any number of removals, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "F2. Lightsabers (medium)",
"description": {
"content": "There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping m",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF958F2"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping m...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "银河议会中动荡不安。数千个恒星系统已宣布意图脱离共和国。海迪大师需要挑选出前往全银河执行维和任务的绝地武士。众所周知，任何维和任务的成功都取决于参与任务的绝地武士光剑的颜色。\n\n海迪面前有 #cf_span[n] 名绝地武士排成一列，每人持有一把颜色属于 #cf_span[m] 种可能颜色之一的光剑。她知道，为了使任务最有效，她需要选出一个连续的武士区间，使得其中恰好有 #cf_span[k1] ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq m \\leq n \\leq 2 \\cdot 10^5 $. \nLet $ C = (c_1, c_2, \\dots, c_n) $ be a sequence of integers, where $ c_i \\in \\{1, 2, \\dots, m\\} $, repre...",
"is_translate": false,
"language": "Formal"
}
]
}