### 问题描述 你有一台拥有 $n$ 个缓存页面空间的服务器，只有 $1$ 个用户在同时使用。这个用户将会一共给出 $m$ 条页面请求。每条请求用一个整数 $y$ 表示请求了页面 $y$。请你计算出对于 $n \in [0, m]$，使用 LRU 页面置换算法的缺页中断次数是多少。 LRU 算法的具体描述为：每次当需要访问一个页面的时候，假设当前用户持有 $n_i$ 个缓存空间，首先查询该页面是否存在 $n_i$ 个缓存页面空间中，若在，则**更新该页面访问时间**并结束；若不存在，则将该页面置入 $n_i$ 个位置的其中一个，并**记录当前访问时间**，并触发一次缺页中断。 置入位置的选择规则如下：如果当前空间中有空的位置（为初始状态，历史未在这个位置插入过任何页面），则选择任意一个空位置插入；否则选择当前在缓存中并且**之前最久**未被访问过的页面（记录的访问时间距离现在最久），在该页面的位置插入新页面。用户的初始缓存页面空间的每个位置均处在初始状态。 ### 输入格式 第一行一个整数，$m$，表示页面请求条数。 接下一行，$m$ 个整数，表示 $m$ 个页面请求的编号。 ### 输出格式 一行，$m+1$ 个整数，表示当缓存大小为 $[0, m]$ 时的答案。 ### 样例输入 ```text 6 1 3 1 2 1 1 ``` ### 样例输出 ```text 6 5 3 3 3 3 3 ``` ### 说明 当缓存大小为 $2$ 时的执行过程如下： 初始：[] 访问：[1] （缺页） 访问：[3, 1] （缺页） 访问：[1, 3] 访问：[2, 1] （缺页） 访问：[1, 2] 访问：[1, 2] 故缺页中断次数为 $3$ 次。 ### 评测数据规模 对于 $30$% 的评测数据，$0 < m \leq 1000$。 对于 $70$% 的评测数据，$0 < m \leq 10^5$。 对于 $100$% 的评测数据，$0 < m, y \leq 10^6$。