Ian and Array Sorting

D. Ian and Array Sorting

Problem

To thank Ian, Mary gifted an array $a$ of length $n$ to Ian. To make himself look smart, he wants to make the array in non-decreasing order by doing the following finitely many times: he chooses two adjacent elements $a_i$ and $a_{i+1}$ ($1\le i\le n-1$), and increases both of them by $1$ or decreases both of them by $1$. Note that, the elements of the array can become negative.

As a smart person, you notice that, there are some arrays such that Ian cannot make it become non-decreasing order! Therefore, you decide to write a program to determine if it is possible to make the array in non-decreasing order.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case consists of a single integer $n$ ($2\le n\le 3\cdot 10^5$) — the number of elements in the array.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, output “YES” if there exists a sequence of operations which make the array non-decreasing, else output “NO”.

You may print each letter in any case (for example, “YES”, “Yes”, “yes”, “yEs” will all be recognized as positive answer).

Example

Input

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

Output

YES
NO
YES
NO
YES

Note

For the first test case, we can increase $a_2$ and $a_3$ both by $1$. The array is now $[1,4,3]$.

Then we can decrease $a_1$ and $a_2$ both by $1$. The array is now $[0,3,3]$, which is sorted in non-decreasing order. So the answer is “YES”.

For the second test case, no matter how Ian perform the operations, $a_1$ will always be larger than $a_2$. So the answer is “NO” and Ian cannot pretend to be smart.

For the third test case, the array is already in non-decreasing order, so Ian does not need to do anything.

Code

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <sstream>//整型转字符串
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=3e5+10;
ll a[N];

void solve()
{
    ll n; 
    cin>>n;
    
    for(ll i=1;i<=n;i++) cin>>a[i];
    
    if(n&1)
    {
        cout<<"YES"<<endl;
        return;
    }
    
    for(ll i=2;i<n;i++)
    {
        if(a[i]!=a[i-1])
        {
            ll idx=a[i]-a[i-1];
            a[i]-=idx;
            a[i+1]-=idx;
        }
    }
    if(a[n-1]<=a[n]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    ll t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}