241981 - 插入排序位置查询

题目描述

给定一个长度为 n 的整数数组 a1, a2, …, an。对它进行从小到大的稳定插入排序。
规定:
第 1 轮:前 1 个元素视为有序。
第 i 轮(2≤i≤n):把原第 i 个元素插入到前 i−1 个已排序元素中,使前 i 个元素有序。
稳定排序:如果两个元素值相等,原来靠前的元素排序后仍然靠前。现在给定 k 和 t,保证 1≤t≤k≤n。
问:第 k 轮结束后,原来第 t 个位置的数现在在第几位?位置从 1 开始编号。

输入

第一行三个整数 n, k, t。第二行 n 个整数,表示原数组 a1, a2, …, an。

输出

输出一个整数,表示答案。

样例

输入

9 5 4
9 2 7 4 1 8 3 6 5

输出

3
说明

1 ≤ n ≤ 1000,1 ≤ t ≤ k ≤ n

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 1 枚
难度 入门


上一题 下一题