"""Original single monotonic max deque; no paired-wedge performance claim."""
from collections import deque
from itertools import product
import json
def maxima(values,width,trace=False):
 if type(values) is not list or len(values)>32 or any(type(x) is not int or abs(x)>1000 for x in values):raise ValueError('bounded integer list')
 if type(width) is not int or width<1 or (values and width>len(values)) or (not values and width!=1):raise ValueError('valid width; empty uses width1')
 q=deque();out=[];steps=[];pushes=0;pops=0
 for i,x in enumerate(values):
  expired=[];dominated=[]
  while q and q[0]<=i-width:expired.append(q.popleft());pops+=1
  while q and values[q[-1]]<x:dominated.append(q.pop());pops+=1
  q.append(i);pushes+=1
  assert all(q[j]<q[j+1] and values[q[j]]>=values[q[j+1]] for j in range(len(q)-1))
  if i>=width-1:out.append({'start':i-width+1,'end_exclusive':i+1,'maximum':values[q[0]],'earliest_max_index':q[0]})
  if trace:steps.append({'index':i,'value':x,'expired_indices':expired,'dominated_indices':dominated,'deque_indices':list(q),'warmup':i<width-1})
 assert pushes==len(values) and pops<=len(values)
 return out,steps,{'pushes':pushes,'pops':pops,'remaining':len(q)}
def oracle(v,w):
 return [{'start':i,'end_exclusive':i+w,'maximum':max(v[i:i+w]),'earliest_max_index':next(j for j in range(i,i+w) if v[j]==max(v[i:i+w]))} for i in range(len(v)-w+1)]
def demo():
 v=[4,2,2,5,1,5];out,tr,ops=maxima(v,3,True);assert out==oracle(v,3);assert [x['maximum'] for x in out]==[4,5,5,5]
 checks=0
 for n in range(1,7):
  for p in product([0,1,2],repeat=n):
   for w in range(1,n+1):
    a,_,_=maxima(list(p),w);assert a==oracle(list(p),w);checks+=1
 assert maxima([],1)[0]==[];same=maxima([2,2,2],2)[0];assert [r['earliest_max_index'] for r in same]==[0,1]
 rejected=[]
 for w in [0,-1,7,True]:
  try:maxima(v,w)
  except ValueError:rejected.append(repr(w))
  else:raise AssertionError('expected rejection')
 return {'values':v,'width':3,'output':out,'trace':tr,'operations_for_this_trace':ops,'all_short_array_width_checks':checks,'equal_values_earliest_index':same,'empty_width1_output':[],'rejected_widths':rejected,'complexity_scope':'amortized pushes/pops, not worst-case constant per update, no timing benchmark','paired_Lemire_wedge_implemented':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))