Codeforces Round #641 (Div. 2) D. Orac and Medians

思路：如果數組存在k，且存在一個區間[i,i+2],至少有兩個數大于等于k，那麼必定有解，否則無解

簡略證明如下：

1.如果存在這麼一個區間，那麼要麼它都變成k，然後拓展把數組所有數都變成k，要麼它都變成x，x>k,然後擴充到k旁邊，在由k擴充，全部變成k，例如n=8，k=2，3 1 3 1 1 1 1 2，那麼可以變成 3 3 3 3 3 3 3 2，然後變成 2 2 2 2 2 2 2 2

2.如果不存在，那麼說明每個[i,i+2]區間最多隻有一個數大于等于k，那麼任何區間，大于等于k的數都不可能占到一半，是以中位數就不可能變成k

 Slime has a sequence of positive integers a1,a2,…,an

.

In one operation Orac can choose an arbitrary subsegment [l…r]

of this sequence and replace all values al,al+1,…,ar to the value of median of {al,al+1,…,ar}

.

In this problem, for the integer multiset s

, the median of s is equal to the ⌊|s|+12⌋-th smallest number in it. For example, the median of {1,4,4,6,5} is 4, and the median of {1,7,5,8} is 5

.

Slime wants Orac to make a1=a2=…=an=k

using these operations.

Orac thinks that it is impossible, and he does not want to waste his time, so he decided to ask you if it is possible to satisfy the Slime's requirement, he may ask you these questions several times.

Input

The first line of the input is a single integer t

: the number of queries.

The first line of each query contains two integers n (1≤n≤100000)

and k (1≤k≤109), the second line contains n positive integers a1,a2,…,an (1≤ai≤109)

The total sum of n

is at most 100000

.

Output

The output should contain t

lines. The i-th line should be equal to 'yes' if it is possible to make all integers k

in some number of operations or 'no', otherwise. You can print each letter in lowercase or uppercase.

Example

Input

Copy

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

Output

Copy

no
yes
yes
no
yes
      

Note

In the first query, Orac can't turn all elements into 3

.

In the second query, a1=6

is already satisfied.

In the third query, Orac can select the complete array and turn all elements into 2

.

In the fourth query, Orac can't turn all elements into 3

.

In the fifth query, Orac can select [1,6]

at first and then select [2,10]

.

#include <cstdio>
#include<iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include<set>
#include<vector>
using namespace std;
#define ll long long
//#define ll int
//#define maxn 1050
#define maxn 1050000
ll a[maxn],n,k;
ll slove()
{
    if(n==1) return 1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=2&&i+j<=n;j++)
        {
            if(a[i]>=k&&a[i+j]>=k) return 1;
        }
    }
    return 0;
}
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll f=0;n,k;
        scanf("%lld %lld",&n,&k);
        for(ll i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            if(a[i]==k) f=1;
        }
        if(f==0)
        {
            printf("no\n");
            continue;
        }
        if(slove()==1) printf("yes\n");
        else printf("no\n");
    }
}