問題文
你知道自古流传下来的日本传统彩票阿弥陀寺吗?
玩阿弥陀寺时,首先 N 在书上画平行垂直线。接下来,M 将书本的水平线画入其中。每条水平线彼此相邻 2 必须绘制书本的垂直线以将它们连接起来。2 同一高度的水平线不得超过一条。在这里,从上面 i (1\,≦\,i\,≦\,M) 从左侧算起的第 3 条水平线 A_i (1\,≦\,A_i < N)第垂直线和 假设我们要连接第 A_i + 1 条垂直线。
N = 5, M = 7, A = \{1,4,3,4,2,3,1\} 案例中的 Amida 彩票如下所示。抽签时,画垂直线 1 选择一本书,然后从上往下走。如果途中遇到水平线,一定要转弯,不要顺着垂直线向上。比如这张阿弥陀寺,从左边开始 如果您从左侧第 4 条垂直线开始抽签 我们到达了第 3 条垂直线。
到目前为止,这都是一个正常的故事,但这些天,“大数据”这个词被谈论得很多。阿弥陀寺未来为了生存,也必须做大,与大数据竞争。
所以,我垂直放置阿弥陀寺。 D 让我们考虑通过将它们连接在一起来制作一个巨大的阿弥陀寺。比如前面提到的阿弥陀寺 如果连接 2 块,它将如下所示。在这种情况下,从左边开始 如果您从第 4 条垂直线开始抽签,您将到达的地方将从左侧开始。 成为第 5 条垂直线。
庞大的阿弥陀彩就这样被创造出来了,但如果阿弥陀彩不能实现它最初的目的,那么做大也是没有意义的。换句话说,如果你不能有效地计算出这个巨型阿弥陀佛的抽奖结果,那么你创造的巨型阿弥陀佛就只是一个涂鸦。
所以, 所有满足1\,≦\,k\,≦\,N 的整数 k 从巨人阿弥陀寺的左边开始 如果您选择第 k 条垂直线并沿着该线移动,我希望您编写一个程序来计算从底部左侧开始的垂直线数。
入力
输入是按以下格式从标准输入给出的。
N M D A_1 A_2 ... A_M
- 1 行是一个整数,表示原始阿弥陀寺中垂直行的数量。 N (2\,≦\,N\,≦\,10^5),表示水平线数的整数 M (0\,≦\,M\,≦\,2 \times 10^5),表示原始阿弥陀佛垂直连接次数的整数 D (1\,≦\,D\,≦\,10^9) 用空格分隔。
- 2 线代表原始阿弥陀寺中水平线的信息。 M 整数 A_i (1\,≦\,i\,≦\,M) 用空格分隔。
部分点
这个问题的测试用例是 4 分为两组,每组都分配分数。
- 1 第三组中,测试用例是 D = 1 满意。如果您正确回答了该组中的所有测试用例, 10 点。
- 2 第三组中,测试用例是 N\,≦\,1,000 和 D\,≦\,1,000 满意。如果您正确回答了该组中的所有测试用例, 20 点。
- 3 第三组中,测试用例是 N\,≦\,8 满意。如果您正确回答了该组中的所有测试用例, 20 点。
- 4 在第二组中,对测试用例没有额外的限制。如果您正确回答了该组中的所有测试用例, 输出 50 点。
出力
N 行。其中 k 在这一排,从巨人阿弥陀寺的左边开始 当您选择第 k 条垂直线并沿着该线移动时,输出一个整数,表示从底端左侧开始到达的垂直线数。
还在输出末尾包含换行符。
入力例1
5 7 1 1 4 3 4 2 3 1
出力例1
4 2 5 3 1
此输入/输出示例对应于问题文本中第一张图所示的 Amidakuji。
入力例2
5 7 2 1 4 3 4 2 3 1
出力例2
3 2 1 5 4
该输入/输出示例是 它对应于第 2 图中所示的阿弥陀寺。这个案例是 1 请注意,不满足第二个测试组的约束。
入力例3
10 20 300 9 1 2 5 8 1 9 3 5 6 4 5 4 6 8 3 2 7 9 6
出力例3
3 7 2 4 5 9 6 1 8 10
这个案例是 1 津和 3 请注意,不满足第二个测试组的约束。