array array array

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

One day, Kaitou Kiddo had stolen a priceless diamond ring. But detective Conan blocked Kiddo's path to escape from the museum. But Kiddo didn't want to give it back. So, Kiddo asked Conan a question. If Conan could give a right answer, Kiddo would return the ring to the museum.
Kiddo: "I have an array $A$ and a number $k$, if you can choose exactly $k$ elements from $A$ and erase them, then the remaining array is in non-increasing order or non-decreasing order, we say $A$ is a magic array. Now I want you to tell me whether $A$ is a magic array. " Conan: "emmmmm..." Now, Conan seems to be in trouble, can you help him?

Input

The first line contains an integer T indicating the total number of test cases. Each test case starts with two integers $n$ and $k$ in one line, then one line with $n$ integers: $A_1,A_2\dots A_n$.
$1\leq T\leq 20$
$1\leq n\leq 10^5$
$0\leq k\leq n$
$1\leq A_i\leq 10^5$

Output

For each test case, please output "A is a magic array." if it is a magic array. Otherwise, output "A is not a magic array." (without quotes).

Sample Input

3 4 1 1 4 3 7 5 2 4 1 3 1 2 6 1 1 4 3 5 4 6

Sample Output

A is a magic array. A is a magic array. A is not a magic array.

Hint

liuyiding

Source

2017 ACM/ICPC Asia Regional Shenyang Online

提交代码