import sys sys.setrecursionlimit(10 ** 6) int1 = lambda x: int(x) - 1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.readline()) def MI(): return map(int, sys.stdin.readline().split()) def LI(): return list(map(int, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def SI(): return sys.stdin.readline()[:-1] class SparseTable: def __init__(self, aa): w = len(aa) h = w.bit_length() table = [aa] + [[-1] * w for _ in range(h - 1)] tablei1 = table[0] for i in range(1, h): tablei = table[i] for j in range(w-(1<mx:mx=e mx=-inf for i,e in enumerate(ee[::-1]): rmx[n-1-i]=mx if e>mx:mx=e #print(lmx) #print(lmn) #print(rmx) #print(rmn) s=0 for j in range(n): for i in range(j): a,b=ee[i],ee[j] if ab:s+=lmx[j] elif lmx[i]>a or st.min(j,n)a:s+=rmx[i] elif rmx[j]>b or st.min(0,i+1)