Codeforces/A_Construct_an_Array.cpp at main · bhavyapuri15/Codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// redcoder.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>
#include <cstring>
#include <numeric>
#include <limits>

using namespace std;

#define ll long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const ll INF = 1e18;
const ll N = 2e5 + 5;

ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; }
ll lcm(ll a,ll b) { return (a/gcd(a,b))*b; }

ll madd(ll a,ll b,ll mod) { return (a%mod+b%mod)%mod; }
ll msub(ll a,ll b,ll mod) { return (a%mod-b%mod+mod)%mod; }
ll mod_mul(ll a,ll b,ll mod) { return (a%mod*b%mod)%mod; }

ll power(ll a,ll b,ll mod)
{
    ll res=1; a%=mod;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

ll modinv(ll a,ll mod) { return power(a,mod-2,mod); }

bool is_prime(ll n)
{
    if(n<2) return false;
    for(ll i=2;i*i<=n;++i) if(n%i==0) return false;
    return true;
}

vector<bool> sieve(ll n)
{
    vector<bool> is_prime(n+1,true);
    is_prime[0]=is_prime[1]=false;
    for(ll i=2;i*i<=n;++i) {
        if(is_prime[i]) {
            for(ll j=i*i;j<=n;j+=i) is_prime[j]=false;
        }
    }
    return is_prime;
}

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for(auto& x : a) cin >> x;

    int l = 0, r = n - 1;
    while(l + 1 < n && a[l] <= a[l+1]) l++;
    while(r - 1 >= 0 && a[r-1] <= a[r]) r--;

    if(l >= r) { yes; return; }

    for(int i = l; i < r; i++)
        if(a[i] > a[i+1]) { no; return; }

    ll lo = 1, hi = INF;
    if(l > 0)   lo = max(lo, a[l-1] - a[l] + 1);
    if(r < n-1) hi = min(hi, a[r+1] - a[r]);

    if(lo <= hi) yes;
    else no;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}