from bisect import bisect_right, bisect_left # instead of AVLTree class BITbisect(): def __init__(self, InputProbNumbers): # 座圧 self.ind_to_co = [-10**18] self.co_to_ind = {} for ind, num in enumerate(sorted(list(set(InputProbNumbers)))): self.ind_to_co.append(num) self.co_to_ind[num] = ind+1 self.max = len(self.co_to_ind) self.data = [0]*(self.max+1) def __str__(self): retList = [] for i in range(1, self.max+1): x = self.ind_to_co[i] if self.count(x): c = self.count(x) for _ in range(c): retList.append(x) return "[" + ", ".join([str(a) for a in retList]) + "]" def __getitem__(self, key): key += 1 s = 0 ind = 0 l = self.max.bit_length() for i in reversed(range(l)): if ind + (1< 0 # 0からiまでの区間和 # 左に進んでいく def _query_sum(self, i): s = 0 while i > 0: s += self.data[i] i -= i & -i return s # i番目の要素にxを足す # 上に登っていく def _add(self, i, x): while i <= self.max: self.data[i] += x i += i & -i # 値xを挿入 def push(self, x): if not x in self.co_to_ind: raise KeyError("The pushing number didnt initialized") self._add(self.co_to_ind[x], 1) # 値xを削除 def delete(self, x): if not x in self.co_to_ind: raise KeyError("The deleting number didnt initialized") if self.count(x) <= 0: raise ValueError("The deleting number doesnt exist") self._add(self.co_to_ind[x], -1) # 要素xの個数 def count(self, x): return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1) # 値xを超える最低ind def bisect_right(self, x): if x in self.co_to_ind: i = self.co_to_ind[x] else: i = bisect_right(self.ind_to_co, x) - 1 return self._query_sum(i) # 値xを下回る最低ind def bisect_left(self, x): if x in self.co_to_ind: i = self.co_to_ind[x] else: i = bisect_left(self.ind_to_co, x) if i == 1: return 0 return self._query_sum(i-1) import sys input = sys.stdin.readline INF = 10**18 N = int(input()) A = list(map(int, input().split())) Bit1 = BITbisect(A) Bit2 = BITbisect(A) ans = INF for a in A: Bit2.push(a) for i, a in enumerate(A): Bit2.delete(a) if i == 0 or i == N-1: Bit1.push(a) continue c1 = Bit1[0] c2 = Bit2[0] if a > c1 and a > c2: ans = min(ans, a+c1+c2) ind1 = Bit1.bisect_left(a) ind2 = Bit2.bisect_left(a) if ind1 < len(Bit1) and ind2 < len(Bit2): b1 = Bit1[ind1] b2 = Bit2[ind2] ans = min(ans, a + b1 + b2) Bit1.push(a) if ans == INF: print(-1) else: print(ans)