Zcmu--1396: queue problem (2)

Description

One of them contains n Queues of elements q, The size of each element meets 1<=xi<=9(0<i<n). Queue has an operation , For the first element of the queue, if the whole queue is the largest, it will be out of the queue , Or join the tail of the team . For a given m, Can you tell me xm Is it the first one out of the queue ？

Input

The first line of input data is an integer T(1<=T<=1000), Represents the number of groups of input data ; The first row of each group of data is two positive integers n Represents the size of the queue and the number of elements (1<n<=1000,0<=m<n), The second line has n Number xi , Represent the size of each element respectively .

Output

For each group of test data , Output xm Is the number of queues .

Sample Input

3

1  0

5

4  2

1  2  3  4

6  0

1  1  9  1  1  1

Sample Output

1

2

5

analysis ： We make use of set To quickly get the maximum element value in the current queue , Because there are elements that repeat , So we have to use multiset Come and save . We can use structures to store elements id and valu value ,c Indicates the number of out of line , If a[ i ]==st.*rbegin() Express a[ i ] Is the largest element in the current queue , List out , If it is xm, Then output c that will do , On the contrary, it is not the maximum , At the end of the team , Corresponding multiset Also delete this element in , So repeatedly until xm List out .

#include <stdio.h>
#include <set>
using namespace std;
struct su
{
	int id;
	int v;
}a[10005];
int main()
{
	int t,i,n,k,c;
	scanf("%d",&t);
	while(t--){
		multiset<int>st;	// establish multiset 
		scanf("%d%d",&n,&k);
		c=1;		// Indicates the number of out of line  
		for(i=0;i<n;i++){
			scanf("%d",&a[i].v);
			a[i].id=i;
			st.insert(a[i].v);	// Deposit in set 
		}
		for(i=0;i<n;i++){
			if(a[i].v==*st.rbegin()){	// Indicates the maximum value of the current queue  
				if(a[i].id==k){		// just xm 
				printf("%d\n",c); 
				break;
			}else st.erase(--st.end()),c++;	// Delete the last element , That's the maximum  
			}else{	// Not the maximum , Simulation to the end of the team  
				a[n].v=a[i].v; 
				a[n++].id=a[i].id;
			}
		}
		st.clear();
	}
	return 0;
}