110002 - Printer Queue

计算机科学学生会中唯一的打印机正经历着极其繁重的工作量。有时打印机队列中有上百个作业,您可能需要等待数小时才能获得一页输出。

由于某些作业比其他作业更重要,黑客将军发明并实现了一个简单的打印作业队列优先级系统。现在,为每个作业分配1到9之间的优先级(9是最高优先级,1是最低优先级),打印机做如下操作。

  • 从队列中取出队列中的第一个作业J。
  • 如果队列中有某个作业的优先级高于作业J,则不打印J并且将J移到队尾。
  • 否则,打印作业J(不要将其放回队列)。

这样,黑客将军正在印刷的所有重要松饼食谱都能很快印刷出来。当然,其他人正在打印的那些烦人的学期论文可能要等很长时间才能打印出来,但这就是生活。

新策略的问题在于,确定打印作业何时实际完成变得相当棘手。你决定写一个程序来解决这个问题。程序将获得当前队列(作为优先级列表)以及作业在队列中的位置,然后必须计算打印作业所需的时间,假设不会向队列中添加其他作业。为了简化问题,我们假设打印作业始终只需一分钟,并且从队列中添加和删除作业是即时的。

输入

一行一个正整数t,表示共t组样例,接下来对于每组样例:

  • 一行两个正整数n和m,n表示打印任务的数量(1<=n<=100),m表示你的任务的位置(0<=m<=n-1)。队列中第一个位置是0。
  • 一行n个范围在1~9之间的正整数,依次表示每个任务的优先级。

输出

对于每组样例,输出一行一个整数,表示你的任务完成打印的时间。

样例

输入

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

输出

1
2
5
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题