class Bit: def __init__(self, n, array=[]): """ :param n: number of elements """ self.n = n self.tree = [0]*(n+1) self.depth = n.bit_length() - 1 for i, a in enumerate(array): self.add(i, a) def get(self,i): """ return summation of elements in [0,i) """ s = 0 i -= 1 while i >= 0: s += self.tree[i] i = (i & (i + 1) )- 1 return s def build(self, array): """ bulid BIT from array """ for i, a in enumerate(array): self.add(i, a) def add(self, i, x): """ add x to i-th element """ while i < self.n: self.tree[i] += x i |= i + 1 def get_range(self,i,j): """ return summation of elements in [i,j) """ if i == 0: return self.get(j) return self.get(j)-self.get(i) def lower_bound(self, x, equal=False): """ return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai ) if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True (Cation) We must assume that A_i>=0 """ sum_ = 0 pos = -1 # 1-indexed の時は pos = 0 if not equal: for i in range(self.depth, -1, -1): k = pos + (1 << i) if k < self.n and sum_ + self.tree[k] < x: # 1-indexed の時は k <= self.n sum_ += self.tree[k] pos += 1 << i if equal: for i in range(self.depth, -1, -1): k = pos + (1 << i) if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n sum_ += self.tree[k] pos += 1 << i return pos, sum_ def __getitem__(self, i): """ [a0, a1, a2, ...] """ if i<0: i=self.n+i return self.get_range(i,i+1) def __iter__(self): """ [a0, a1, a2, ...] """ for i in range(self.n): yield self.get_range(i,i+1) def __str__(self): text1 = " ".join(["element: "] + list(map(str, self))) text2 = " ".join(["cumsum(1-indexed): "]+list(str(self.get(i)) for i in range(1,self.n+1))) return "\n".join((text1, text2)) class BitImos: def __init__(self, n, array=[]): self.n = n self.p = Bit(self.n + 1) self.q = Bit(self.n + 1) for i, a in enumerate(array): self.add(i, a) def add(self, s, x): self.add_range(s,s+1,x) def add_range(self, s, t, x): """ add x to a close-interval [s,t)""" self.p.add(s, -x * s) self.p.add(t, x * t) self.q.add(s, x) self.q.add(t, -x) def build(self, array): """ bulid BIT from array """ for i, a in enumerate(array): self.add(i, a) def get(self,s): return self.get_range(s,s+1) def get_range(self,s,t): """ return summation of elements in [s,t) """ return self.p.get(t)+self.q.get(t)*t-self.p.get(s)-self.q.get(s)*s def __getitem__(self, s): """ return s-th element of array (not sum-array) """ return self.q.get(s+1) def __iter__(self): """ max(self) returns what we obtain by the Imos method""" for t in range(self.n): yield self.q.get(t+1) def __str__(self): text1 = " ".join(["element: "] + list(map(str, self))) return text1 class SortedList: def __init__(self, n, A=[]): """ :param n: miximum value of A self.size: number of elements in BitSet """ self.n = n self.p = Bit(self.n + 1) self.size = 0 self.flip = 0 for a in A: self.add(a) def add(self,x): self.p.add(x, 1) self.size += 1 self.flip += self.size - self.p.get(x+1) # we can remove this if we do not use flip_number def remove(self,x): self.p.add(x, -1) self.size -= 1 def bisect_left(self,x): """ return bisect_left(sorted(B),x) """ if x <= self.n: return self.p.get(x) else: return self.size def bisect_right(self,x): """ return bisect_right(sorted(B),x) """ x += 1 if x <= self.n: return self.p.get(x) else: return self.size def flip_counter(self): return self.flip def count(self,x): return self.p[x] def count_range(self,l,r): """ return number of elements in closed set [l,r]""" return self.bisect_right(r)-self.bisect_left(l) def minimum(self,k=1): """ return k-th minimum value """ if k <= self.size: return self.p.lower_bound(k)[0] + 1 else: sys.stderr.write("minimum: list index out of range (k={0})\n".format(k)) def min(self): return self.minimum(1) def max(self): return self.p.lower_bound(self.size)[0] + 1 def upper_bound(self,x,equal=False): """ return maximum element lower than x """ k = self.p.get(x+equal) if k: return self.minimum(k) else: sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x)) def lower_bound(self,x,equal=False): """ return minimum element greater than x """ k =self.p.get(x+1-equal)+1 if k <= self.size: return self.minimum(k) else: sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x)) def __getitem__(self, k): """ return k-th minimum element (0-indexed) B[k] = sorted(A)[k] """ if len(self)==0: sys.stderr.write("__getitem__: no elements exist in this BitSet\n") elif k >= len(self): sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1)) elif k >= 0: return self.minimum(k+1) else: sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k)) def __len__(self): return self.size def __iter__(self): """ return sorted list """ for i in range(self.n+1): if self.p[i]: for _ in range(self.p[i]): yield i def __str__(self): """ return sorted list """ text1 = " ".join(list(map(str, self))) return "[" + text1 + "]" class SortedList2: """ if we need compress """ def __init__(self, data, A=[]): """ self.size: number of elements in BitSet """ self.data = sorted(list(set(data))) self.n = len(self.data) self.p = Bit(self.n + 1) self.size = 0 self.flip = 0 self.code = {} self.decode = [] for i, b in enumerate(self.data): self.code[b] = i self.decode.append(b) for a in A: self.add(a) def add(self,x): self.p.add(self.code[x], 1) self.size += 1 self.flip += self.size - self.p.get(self.code[x]+1) # we can remove this if we do not use flip_number def remove(self,x): self.p.add(self.code[x], -1) self.size -= 1 def bisect_left(self,x): """ return bisect_left(sorted(B),x) """ if x in self.code.keys(): return self.p.get(self.code[x]) else: return self.p.get(bisect_right(self.data,x)) def bisect_right(self,x): """ return bisect_right(sorted(B),x) """ x += 1 if x in self.code.keys(): return self.p.get(self.code[x]) else: return self.p.get(bisect_right(self.data,x)) def count(self,x): return self.p[self.code[x]] def count_range(self,l,r): """ return number of elements in closed set [l,r]""" return self.bisect_right(r)-self.bisect_left(l) def minimum(self,k=1): """ return k-th minimum value """ if k <= self.size: return self.decode[self.p.lower_bound(k)[0] + 1] else: sys.stderr.write("minimum: list index out of range (k={0})\n".format(k)) def min(self): return self.minimum(1) def max(self): return self.decode[self.p.lower_bound(self.size)[0] + 1] def upper_bound(self,x,equal=False): """ return maximum element lower than x """ if x in self.code.keys(): y = self.code[x] + equal else: y = bisect_right(self.data, x) k = self.p.get(y) if k: return self.minimum(k) else: sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x)) def lower_bound(self,x,equal=False): """ return minimum element greater than x """ if x in self.code.keys(): y = self.code[x] + 1 - equal else: y = bisect_left(self.data, x) k =self.p.get(y)+1 if k <= self.size: return self.minimum(k) else: sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x)) def nearest(self,x,k): """ return k-th nearest value to x """ if k>len(self): sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k)) return def test(d): r=self.bisect_right(x+d)-1 l=self.bisect_left(x-d) return r-l+1<=k ok,ng=0,10**18+1 while abs(ok-ng)>1: mid=(ok+ng)//2 if test(mid): ok=mid else: ng=mid d=ok r=self.bisect_right(x+d)-1 l=self.bisect_left(x-d) if d==0: R=self.lower_bound(x,equal=True) L=self.upper_bound(x,equal=True) if abs(x-L)==abs(R-x): if self.count(L)>=k: return L else: return R elif abs(x-L)=len(self)-1: return self[l-1] else: R=self[r+1] L=self[l-1] if abs(x-L)==abs(R-x): if self.count(L)>=k-(r-l+1): return L else: return R elif abs(x-L)= len(self): sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1)) elif k >= 0: return self.minimum(k+1) else: sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k)) def __len__(self): return self.size def __iter__(self): """ return sorted list """ for i in range(self.n+1): if self.p[i]: for _ in range(self.p[i]): yield self.decode[i] def __str__(self): """ return sorted list """ text1 = " ".join(list(map(str, self))) return "[" + text1 + "]" ################################################### def example(): global input example = iter( """ 6 10 5 1 5 10 7 """ .strip().split("\n")) input = lambda: next(example) ################################################### import sys input = sys.stdin.readline from bisect import bisect_left, bisect_right # example() N=int(input()) A=list(map(int, input().split())) INF=float("inf") left_u=[-1]*N left_d=[INF]*N u,d=-1,INF for i in range(N): if u>A[i]: left_u[i]=u if dA[i]: right_u[i]=u if d