######################################## from heapq import heappush, heappop def dijkstra( G, s, INF=10 ** 18): """ https://tjkendev.github.io/procon-library/python/graph/dijkstra.html O((|E|+|V|)log|V|) V: 頂点数 G[v] = [(nod, cost)]: 頂点vから遷移可能な頂点(nod)とそのコスト(cost) s: 始点の頂点""" N=len(G) N+=1 dist = [INF] * N hp = [(0, s)] # (c, v) dist[s] = 0 while hp: c, v = heappop(hp) #vまで行くコストがc if dist[v] < c: continue for u, cost in G[v]: if dist[v] + cost < dist[u]: dist[u] = dist[v] + cost heappush(hp, (dist[u], u)) return dist ################################################## n=int(input()) a=[10**12]+list(map(int,input().split()))+[10**12] root=[[] for i in range(n+3)] s=n+2 root[s].append((1,0)) root[s].append((n,0)) for i in range(1,n+1): if a[i-1]