Problem:
 Score : 700 points    Problem Statement Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1) .  Now, he will perform the following operation exactly once :   Choose K consecutive elements in P and sort them in ascending order.   Find the number of permutations that can be produced as P after the operation.      Constraints  2 \leq N \leq 200000  2 \leq K \leq N  0 \leq P_i \leq N-1  P_0,P_1,\cdots,P_{N-1} are all different.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  P_0  P_1  \cdots  P_{N-1}       Output Print the number of permutations that can be produced as P after the operation.        Sample Input 1 5 3
0 2 1 4 3      Sample Output 1 2  Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4) .       Sample Input 2 4 4
0 1 2 3      Sample Output 2 1       Sample Input 3 10 4
2 0 1 3 7 5 4 6 8 9      Sample Output 3 6

Solution (Python):
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep+1:]:
            self.append(t)
        for t in data[sep::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    __slots__=('unit','f','fold_r','fold_l','data_r','data_l')
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    __slots__=('unit','f','fold_r','fold_l','data_r','data_l')
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        list(map(self.append,data[sep:]))
        list(map(self.appendleft,data[sep-1::-1]))
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        *_,=map(self.append,data[sep:])
        *_,=map(self.appendleft,data[sep-1::-1])
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        *_,=map(self.append,data[sep:])
        *_,=map(self.appendleft,data[sep-1::-1])
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        sep=len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__init__(self.unit,self.f,self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__init__(self.unit,self.f,self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r,self.fold_l=[unit],[unit]
        self.data_r,self.data_l=[],[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):temp.append(self.popleft())
        for _ in range(n//2,n):self.append(self.popleft())
        for t in temp[::-1]:self.appendleft(t)
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):temp.append(self.pop())
        for _ in range(n//2,n):self.appendleft(self.pop())
        for t in temp[::-1]:self.append(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        *_,=map(temp.append,(self.popleft()for _ in range(n//2)))
        *_,=map(self.append,(self.popleft()for _ in range(n//2,n)))
        *_,=map(self.appendleft,temp[::-1])
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        *_,=map(temp.append,(self.pop()for _ in range(n//2)))
        *_,=map(self.appendleft,(self.pop()for _ in range(n//2,n)))
        *_,=map(self.append,temp[::-1])
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):
            temp.append(self.popleft())
        for _ in range(n//2,n):
            self.append(self.popleft())
        for _ in range(n//2):
            self.appendleft(temp.pop())
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):
            temp.append(self.pop())
        for _ in range(n//2,n):
            self.appendleft(self.pop())
        for _ in range(n//2):
            self.append(temp.pop())
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):
            temp.append(self.popleft())
        for _ in range(n//2,n):
            self.append(self.popleft())
        for _ in range(n//2):
            self.appendleft(temp.pop())
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):
            temp.append(self.pop())
        for _ in range(n//2,n):
            self.appendleft(self.pop())
        for _ in range(n//2):
            self.append(temp.pop())
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):
            temp.append(self.popleft())
        for _ in range(n//2,n):
            self.append(self.popleft())
        for t in temp[::-1]:
            self.appendleft(t)
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):
            temp.append(self.pop())
        for _ in range(n//2,n):
            self.appendleft(self.pop())
        for t in temp[::-1]:
            self.append(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,lambda a,b:a if a<b else b)
s_max=SWAG(0,lambda a,b:a if a>b else b)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):
            temp.append(self.popleft())
        for _ in range(n//2,n):
            self.append(self.popleft())
        for t in temp[::-1]:
            self.appendleft(t)
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):
            temp.append(self.pop())
        for _ in range(n//2,n):
            self.appendleft(self.pop())
        for t in temp[::-1]:
            self.append(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):
            temp.append(self.popleft())
        for _ in range(n//2,n):
            self.append(self.popleft())
        for t in temp[::-1]:
            self.appendleft(t)
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):
            temp.append(self.pop())
        for _ in range(n//2,n):
            self.appendleft(self.pop())
        for t in temp[::-1]:
            self.append(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
from heapq import heappush, heappop

N, K = map(int, input().split())
P = [int(i) for i in input().split()]

dp = [0] * N
dp[0] = 1
for i in range(1, N) :
    if P[i] > P[i-1] :
        dp[i] = dp[i-1] + 1
    else :
        dp[i] = 1
        
ma = []
mi = []

for i in range(K) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))

if dp[K-1] == K :
    ret = 0
else :
    ret = 1
    
for i in range(K, N) :
    heappush(ma, (-P[i], i))
    heappush(mi, (P[i], i))
    
    while ma[0][1] < i - K :
        heappop(ma)
    while mi[0][1] < i - K :
        heappop(mi)
        
    if dp[i] < K and (P[i-K] != mi[0][0] or P[i] != -ma[0][0]) :
        ret += 1

if sum([dp[i] >= K for i in range(N)]) > 0 :
    ret += 1

print(ret)

Solution (Python):
from collections import deque
from itertools import accumulate

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

N, K, *P = map(int, open(0).read().split())

mi = slide_min(P, K)
ma = slide_min([-p for p in P], K)

B = [mi != i or ma != i + K for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]

A = [0] + list(accumulate(x < y for x, y in zip(P, P[1:])))
S = [y - x != K - 1 for x, y in zip(A, A[K - 1:])]

ans = 1 + sum(b for b, s in zip(B, S[1:]) if s)
if S[0] and not all(S):
    ans += 1
print(ans)

Solution (Python):
from itertools import accumulate
from collections import deque

N, K, *P = map(int, open(0).read().split())

def slide(A, K, cmp=lambda a, b: a > b):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and cmp(A[Q[-1]], a):
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

mi = slide(P, K)
ma = slide(P, K, lambda a, b: a < b)

B = [mi != i or ma != i + K for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]

A = [0] + list(accumulate(x < y for x, y in zip(P, P[1:])))
S = [y - x != K - 1 for x, y in zip(A, A[K - 1:])]

ans = 1 + sum(b for b, s in zip(B, S[1:]) if s)
if S[0] and not all(S):
    ans += 1
print(ans)

Solution (Python):
from itertools import accumulate
from collections import deque

N, K, *P = map(int, open(0).read().split())

mi = []
Q = deque()
for i, p in enumerate(P):
    while Q and P[Q[-1]] > p:
        Q.pop()
    Q.append(i)
    if Q[0] == i - K:
        Q.popleft()
    mi.append(Q[0])

ma = []
Q = deque()
for i, p in enumerate(P):
    while Q and P[Q[-1]] < p:
        Q.pop()
    Q.append(i)
    if Q[0] == i - K:
        Q.popleft()
    ma.append(Q[0])

mi = mi[K - 1:]
ma = ma[K - 1:]

B = [mi[i] != i or ma[i + 1] != i + K for i in range(N - K)]

A = [0] + list(accumulate(x < y for x, y in zip(P, P[1:])))
S = [y - x != K - 1 for x, y in zip(A, A[K - 1:])]

ans = 1 + sum(b for b, s in zip(B, S[1:]) if s)
if S[0] and not all(S):
    ans += 1
print(ans)

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
def main():
  def update(k,x):
    k+=N0-1
    data_min[k]=data_max[k]=x
    while k>=0:
      k=(k-1)//2
      a,b=data_min[2*k+1],data_min[2*k+2]
      data_min[k]=a if a<b else b
      a,b=data_max[2*k+1],data_max[2*k+2]
      data_max[k]=a if a>b else b
  def query_min(l,r):
    L,R=l+N0,r+N0
    s=INF
    while L<R:
      if R&1:
        R-=1
        t=data_min[R-1]
        if t<s:s=t
      if L&1:
        t=data_min[L-1]
        if t<s:s=t
        L+=1
      L//=2
      R//=2
    return s
  def query_max(l,r):
    L,R=l+N0,r+N0
    s=0
    while L<R:
      if R&1:
        R-=1
        t=data_max[R-1]
        if t>s:s=t
      if L&1:
        t=data_max[L-1]
        if t>s:s=t
        L+=1
      L//=2
      R//=2
    return s
  n,k,*p=map(int,open(0).read().split())
  N0=2**(n-1).bit_length()
  INF=10**18
  data_min=[INF]*2*N0
  data_max=[0]*2*N0
  c=[0]
  for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
  *c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
  x=not f
  for i,q in enumerate(p):update(i,q)
  for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    if not c and(a!=query_min(i,i+k)or b!=query_max(i+1,i+k+1)):x+=1
  print(x+f)
main()
"""))