You've got an array, consisting of n integers a_1, a_2, ..., a_{n}. Also, you've got m queries, the i-th query is described by two integers l_{i}, r_{i}. Numbers l_{i}, r_{i} define a subsegment of the original array, that is, the sequence of numbers a_{l}_{i}, a_{l}_{i} + 1, a_{l}_{i} + 2, ..., a_{r}_{i}. For each query you should check whether the corresponding segment is a ladder. 

A ladder is a sequence of integers b_1, b_2, ..., b_{k}, such that it first doesn't decrease, then doesn't increase. In other words, there is such integer x (1 ≤ x ≤ k), that the following inequation fulfills: b_1 ≤ b_2 ≤ ... ≤ b_{x} ≥ b_{x} + 1 ≥ b_{x} + 2... ≥ b_{k}. Note that the non-decreasing and the non-increasing sequences are also considered ladders.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of array elements and the number of queries. The second line contains the sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where number a_{i} stands for the i-th array element.

The following m lines contain the description of the queries. The i-th line contains the description of the i-th query, consisting of two integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the boundaries of the subsegment of the initial array.

The numbers in the lines are separated by single spaces.


-----Output-----

Print m lines, in the i-th line print word "Yes" (without the quotes), if the subsegment that corresponds to the i-th query is the ladder, or word "No" (without the quotes) otherwise. 


-----Examples-----
Input
8 6
1 2 1 3 3 5 2 1
1 3
2 3
2 4
8 8
1 4
5 8

Output
Yes
Yes
No
Yes
No
Yes

Difficulty: interview

Starter code:

Solutions:
import sys
n,m=list(map(int,sys.stdin.readline().split()))
M=[m]
A=list(map(int,sys.stdin.readline().split()))
L=[0]*n
inc=False
dec=False
def ALLYes():
    Ans=""
    for i in range(M[0]):
        Ans+="Yes\n"
    sys.stdout.write(Ans)
    return
for i in range(1,n):
    if(A[i]>A[i-1]):
        L[i]=1
        inc=True
    elif(A[i]==A[i-1]):
        L[i]=0
    else:
        L[i]=-1
        dec=True
if(inc==False or dec==False):
    ALLYes()
else:
    neg=L.index(-1)
    pos=L.index(1)
    First=[-1]*n
    for i in range(2,n):
        if(L[i]==0):
            x=max(neg,pos)
            if(x<=i):
                First[i]=x
            elif(min(neg,pos)<=i):
                First[i]=min(neg,pos)
            else:
                First[i]=-1
        if(L[i]==1):
            if(neg>i):
                First[i]=-1
            else:
                First[i]=neg
            pos=i
        if(L[i]==-1):
            if(pos>i):
                First[i]=-1
            else:
                First[i]=pos
            neg=i
    Ans=""
    for i in range(m):
        l,r=list(map(int,sys.stdin.readline().split()))
        r-=1
        if(r-l<1):
            Ans+="Yes\n"
            continue
        if(L[r]==0):
            r=First[r]
            if(r<1):
                Ans+="Yes\n"
                continue
        if(L[r]==1):
            r=First[r]
            if(r<l):
                Ans+="Yes\n"
                continue
            else:
                Ans+="No\n"
                continue
        elif(L[r]==-1):
            r=First[r]
            if(r<l):
                Ans+="Yes\n"
                continue
            r=First[r]
            if(r<l):
                Ans+="Yes\n"
                continue
            else:
                Ans+="No\n"
                continue
    sys.stdout.write(Ans)
    
    


M = lambda: map(int, input().split())
L = lambda: list(map(int, input().split()))
I = lambda: int(input())

n, k = M()
t = [0] + L()
a, b = list(range(n + 1)), list(range(n + 1))
for i in range(n, 1, -1):
    if t[i] >= t[i - 1]: a[i - 1] = a[i]
    if t[i] <= t[i - 1]: b[i - 1] = b[i]
p = ['No'] * k
for i in range(k):
    x, y = M()
    if b[a[x]] >= y: p[i] = 'Yes'
print('\n'.join(p))

import sys

n,m=list(map(int,sys.stdin.readline().split()))

L=list(map(int,sys.stdin.readline().split()))

R=[0]*n
K=[0]*n
p=0

for i in range(1,n):
    if(L[i]<L[i-1]):
        for j in range(p,i):
            R[j]=i
        p=i
for j in range(p,n):
    R[j]=n
p=0
for i in range(1,n):
    if(L[i]>L[i-1]):
        for j in range(p,i):
            K[j]=i
        p=i
for j in range(p,n):
    K[j]=n
for i in range(m):
    x,y=list(map(int,sys.stdin.readline().split()))
    x-=1
    y-=1
    r=R[x]
    if(r>=y):
        sys.stdout.write("Yes\n")
        continue
    e=K[r]
    if(e>y):
        sys.stdout.write("Yes\n")
        continue
    sys.stdout.write("No\n")
    


def main():
    from sys import stdin, stdout
    (n, m) = list(map(int, stdin.readline().strip().split(' ')))
    a = [0] + list(map(int, stdin.readline().strip().split(' ')))
    r = [0] * (n + 1) # r[i] stores highest index to right of i st. i..ri is nondecreasing
    l = [0] * (n + 1) # l[i] stores smallest index to the left of i st. li..i is nonincreasing

    l[1] = 1
    r[n] = n

    for i in range(2, n + 1):
        if a[i - 1] >= a[i]:
            l[i] = l[i - 1]
        else:
            l[i] = i

    for i in range(n - 1, 0, -1):
        if a[i + 1] >= a[i]:
            r[i] = r[i + 1]
        else:
            r[i] = i

    for i in range(m):
        (a, b) = list(map(int, stdin.readline().strip().split(' ')))
        if r[a] >= l[b]:
            stdout.write("Yes\n")
        else:
            stdout.write("No\n")
main()


import sys



n,m=list(map(int,sys.stdin.readline().split()))



L=list(map(int,sys.stdin.readline().split()))



R=[0]*n

K=[0]*n

p=0



for i in range(1,n):

    if(L[i]<L[i-1]):

        for j in range(p,i):

            R[j]=i

        p=i

for j in range(p,n):

    R[j]=n

p=0

for i in range(1,n):

    if(L[i]>L[i-1]):

        for j in range(p,i):

            K[j]=i

        p=i

for j in range(p,n):

    K[j]=n

for i in range(m):

    x,y=list(map(int,sys.stdin.readline().split()))

    x-=1

    y-=1

    r=R[x]

    if(r>=y):

        sys.stdout.write("Yes\n")

        continue

    e=K[r]

    if(e>y):

        sys.stdout.write("Yes\n")

        continue

    sys.stdout.write("No\n")

    





# Made By Mostafa_Khaled


n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
l1=[0]*(n)
l3=[0]*n
f=False
v=0
for i in range(1,n) :
    if l[i]<l[i-1] :
        f=True
        v=i
    if l[i]>l[i-1] and f :
        f=False
        for j in range(i-1,v-1,-1) :
            l3[j]=j
        l1[v]=1
        v=-1
    
l2=[0]*(n)
for i in range(1,n) :
    l2[i]=l1[i]+l2[i-1]
s=[]
for i in range(m) :
    a,b=list(map(int,input().split()))
    t=l2[b-1]-l2[a-1]
    
    if l3[b-1]>=b-1 :
        t-=1
    
    if t>0 :
        s.append("No")
    else :
        s.append("Yes")
print("\n".join(s))


'''input
8 6
1 2 1 3 3 5 2 1
1 3
2 3
2 4
8 8
1 4
5 8
'''
from sys import stdin
import sys
import copy
sys.setrecursionlimit(15000)


def create_dp(arr, n):
	dp1 = [-1] * n
	dp1[-1] = n - 1

	for i in range(n - 2, -1, -1):
		if arr[i] <= arr[i + 1]:
			dp1[i] = dp1[i + 1]
		else:
			dp1[i] = i

	dp2 = [-1] * n
	dp2[-1] = n - 1
	for i in range(n - 2, -1, -1):
		if arr[i] >= arr[i + 1]:
			dp2[i] = dp2[i + 1]
		else:
			dp2[i] = i
	return dp1, dp2


# main starts
n, m = list(map(int, stdin.readline().split()))
arr = list(map(int, stdin.readline().split()))
dp1, dp2 = create_dp(arr, n)
for _ in range(m):
	l, r = list(map(int, stdin.readline().split()))
	if dp2[dp1[l - 1]] >= r - 1:
		print("Yes")
	else:
		print("No")

from sys import stdin

input = stdin.readline

[n, q] = [int(item) for item in input().split(' ')]
arr = [int(item) for item in input().split(' ')]
queries = [[int(item) for item in input().split(' ')] for i in range(q)]

b = [1]

for i in range(1, n):
    b.append((b[-1] + 1) if arr[i] <= arr[i - 1] else 1)

c = [1]
for i in reversed(list(range(n - 1))):
    c.append(c[-1] + 1 if arr[i] <= arr[i + 1] else 1)
c = [item for item in reversed(c)]

for query in queries:
    (x, y) = query
    x -= 1
    y -= 1
    print('Yes' if (x + c[x] > y) or (y - b[y] < x) or (x + c[x] > y - b[y]) else 'No')
"""
5 1
1 3 3 2 2
1 4

5 1
1 2 2 1 1
1 4

5 1
2 2 1 1 2
1 5
"""


import sys

# inf = float("inf")
# sys.setrecursionlimit(10000000)

# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# mod, MOD = 1000000007, 998244353
# words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'quarter',16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',25:'twenty five',26:'twenty six',27:'twenty seven',28:'twenty eight',29:'twenty nine',30:'half'}
# vow=['a','e','i','o','u']
# dx,dy=[0,1,0,-1],[1,0,-1,0]

# import random
# from collections import deque, Counter, OrderedDict,defaultdict
# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pi,gcd
# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right

def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n,m = get_ints()
Arr = get_array()
up = [i for i in range(n)]
down = [i for i in range(n)]
for i in range(1,n):
    if Arr[i-1]<=Arr[i]:
        up[i] = up[i-1]
    if Arr[i-1]>=Arr[i]:
        down[i] = down[i-1]
while m:
    l,r = get_ints()
    if (l-1)>=up[down[r-1]]:
        print('Yes')
    else:
        print('No')
    m-=1

import sys

# inf = float("inf")
# sys.setrecursionlimit(10000000)

# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# mod, MOD = 1000000007, 998244353
# words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'quarter',16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',25:'twenty five',26:'twenty six',27:'twenty seven',28:'twenty eight',29:'twenty nine',30:'half'}
# vow=['a','e','i','o','u']
# dx,dy=[0,1,0,-1],[1,0,-1,0]

# import random
# from collections import deque, Counter, OrderedDict,defaultdict
# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pi,gcd
# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right

def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n,m = get_ints()
Arr = get_array()
up = [i for i in range(n)]
down = [i for i in range(n)]
for i in range(1,n):
    if Arr[i-1]<=Arr[i]:
        up[i] = up[i-1]
    if Arr[i-1]>=Arr[i]:
        down[i] = down[i-1]
while m:
    l,r = get_ints()
    if (l-1)>=up[down[r-1]]:
        print('Yes')
    else:
        print('No')
    m-=1

import math,sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda:int(input())
li = lambda:list(map(int,input().split()))

def case():
	n,q=li()
	a=li()
	up=[0]*n
	down=[0]*n 
	i=0
	while(i<n):
		j=i 
		while(j<n-1 and a[j]<=a[j+1]):
			j+=1
		for k in range(i,j+1):
			up[k]=j 
		i=j+1
	i=0
	while(i<n):
		j=i 
		while(j<n-1 and a[j]>=a[j+1]):
			j+=1
		for k in range(i,j+1):
			down[k]=j
		i=j+1
	for i in range(q):
		l,r=li()
		p=up[l-1]
		q=down[p]
		if(q+1>=r):
			print("Yes")
		else:
			print("No")


		

for _ in range(1):
	case()

import sys
input=sys.stdin.readline
a,b=list(map(int,input().split()))
z=list(map(int,input().split()))
ans=[0]
for i in range(1,len(z)):
    if(z[i]>z[i-1]):
        ans.append(1)
    elif(z[i]<z[i-1]):
        ans.append(2)
    else:
        ans.append(0)

start=[0 for i in range(len(ans))]
for i in range(len(ans)-1,-1,-1):
    if(ans[i]==2):
        start[i]=i
    else:
        if(i==len(ans)-1):
            start[i]=-1
        else:
            start[i]=start[i+1]
end=[0 for i in range(len(ans))]
for i in range(len(ans)):
    if(ans[i]==1):
        end[i]=i
    else:
        if(i==0):
            end[i]=-1
        else:
            end[i]=end[i-1]

for i in range(b):
    l,r=list(map(int,input().split()))
    if(l==len(z)):
        print('Yes')
        continue;
    if(start[l]==-1 or end[r-1]==-1):
        print('Yes')
    else:
        if(start[l]>end[r-1]):
            print('Yes')
        else:
            print('No')
    


n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))
up = [i for i in range(n)]
down = [i for i in range(n)]

for i in range(1, n):
    if arr[i-1] <= arr[i]:
        up[i] = up[i-1]
    if arr[i-1] >= arr[i]:
        down[i] = down[i-1]

all_res = []
seg = list(tuple(list(map(int, input().split())) for _ in range(m)))
for l, r in seg:
    if l - 1 >= up[down[r - 1]]:
        all_res.append('Yes')
    else:
        all_res.append('No')
print('\n'.join(all_res))


n,m=map(int,input().split())
*a,=map(int,input().split())
inc=[*range(n)]
dec=[*range(n)]
for i in range(n-1,0,-1):
    if a[i]>=a[i-1]:inc[i-1]=inc[i]
    if a[i]<=a[i-1]:dec[i-1]=dec[i]
k=['No']*m
l=0
for i,j in (map(lambda i: int(i)-1,input().split()) for _ in ' '*m):
    if dec[inc[i]]>=j: k[l]='Yes'
    l+=1
print('\n'.join(k))

import os

def __starting_point():
    n, m = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    increase = [-1] * n
    decrease = [-1] * n
    tmp = n - 1
    for i in range(n - 1, -1, -1):
        if i != n - 1:
            if arr[i] > arr[i + 1]:
                tmp = i
        increase[i] = tmp
    tmp = 0
    for i in range(n):
        if i != 0:
            if arr[i - 1] < arr[i]:
                tmp = i
        decrease[i] = tmp
    result = []
    for i in range(m):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        result.append("Yes\n" if increase[a] >= decrease[b] else "No\n")

    print("".join(result))

__starting_point()

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Aug  1 18:08:37 2020

@author: divyarth
"""

import sys
import heapq
from collections import deque
from collections import defaultdict
input=sys.stdin.readline
print=sys.stdout.write
sys.setrecursionlimit(100000)
def PRINT(lst,sep=' '): print(sep.join(map(str,lst)))
I=lambda : list(map(int,input().split(' ')))

def solve(lst,queries):
    
    n=len(lst)
    arr_f=[1]
    cur_max=1
    for i in range(n-2,-1,-1):
        if lst[i]<=lst[i+1]:
            cur_max+=1
        else:
            cur_max=1
        arr_f.append(cur_max)
    arr_f.reverse()
        
    arr_b=[1]
    cur_max=1
    for i in range(n-1):
        if lst[i+1]<=lst[i]:
            cur_max+=1
        else:
            cur_max=1
        arr_b.append(cur_max)
    
    ans=[]
    for l,r in queries:
        l=l-1
        r=r-1
        if arr_f[l]+arr_b[r]>=r-l+1:
            ans.append('Yes')
        else:
            ans.append('No')
    PRINT(ans,sep='\n')
    
n,m=I()
lst=I()
queries=[I() for i in range(m)]
solve(lst,queries)

[n, q]=list(map(int, input().split()))
arr=list(map(int, input().split()))
interval=[idx for idx in range(n)]
l ,r = 0, 1
while(l<=r and r<n):
    while(r<n and arr[r]>=arr[r-1]):
        r+=1
    last=r
    while(r<n and arr[r]<=arr[r-1]):
        if(arr[r]!=arr[last]):
            last=r
        r+=1
    for idx in range(l, r):
        interval[idx]=max(interval[idx], r-1)
    l=last

ans=[]
for _ in range(q):
    [l, r]=list(map(int, input().split()))
    if(interval[l-1]>=r-1):
        ans.append('Yes')
    else:
        ans.append('No')
for x in ans:
    print(x)

from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
from collections import deque
n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[0]+l
a=[0 for i in range(n+1)]
a[-1]=n
b=list(a)
for i in range(n-1,0,-1):
	if l[i]<=l[i+1]:
		a[i]=a[i+1]
	else:
		a[i]=i
	if l[i]>=l[i+1]:
		b[i]=b[i+1]
	else:
		b[i]=i
# print(a)
# print(b)
for i in range(m):
	x,y=map(int,input().split())
	if b[a[x]]>=y:
		print("Yes")
	else:
		print("No")