package contest200417; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; // O(n) public class E2 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int n = ni(); int[] a = na(n); out.println(go(a) + go(rev(a))); } public static int[] rev(int[] a){int[] b = new int[a.length];for(int i = 0;i < a.length;i++)b[a.length-1-i] = a[i];return b;} long go(int[] a) { int n = a.length; int[] larger = enumPrevWall(a); int[] smaller = enumPrevShutter(a); int[] par = new int[n+1]; for(int i = 0;i < n;i++){ par[i] = larger[i] == -1 ? n : larger[i]; } par[n] = -1; int[][] g = parentToG(par); int[][] pars = parents3(g, n); int[] dep = pars[2]; int[][] qs = new int[n][]; long ans = 0; int p = 0; for(int i = 0;i < n;i++){ int s = smaller[i]; if(s != -1)qs[p++] = new int[]{i, smaller[i], -1}; ans += dep[i]; } ans -= n; lcabatch(g, n, Arrays.copyOf(qs, p)); for(int i = 0;i < p;i++){ ans -= dep[qs[i][2]]; } return ans; } static void lcabatch(int[][] g, int root, int[][] qs) { int n = g.length; int[] ps = new int[n]; for(int[] q : qs){ assert q.length == 3; ps[q[0]]++; ps[q[1]]++; } int[][][] qg = new int[n][][]; for(int i = 0;i < n;i++)qg[i] = new int[ps[i]][]; for(int[] q : qs){ qg[q[0]][--ps[q[0]]] = q; qg[q[1]][--ps[q[1]]] = q; } lcadfs(root, -1, g, qg, new DJSet(n), new int[n], new boolean[n]); } static void lcadfs(int u, int par, int[][] g, int[][][] qg, DJSet ds, int[] anc, boolean[] black) { anc[u] = u; for(int v : g[u]){ if(v == par)continue; lcadfs(v, u, g, qg, ds, anc, black); ds.union(u, v); anc[ds.root(u)] = u; } black[u] = true; for(int[] q : qg[u]){ int v = u^q[0]^q[1]; if(black[v])q[2] = anc[ds.root(v)]; } } public static class DJSet { public int[] upper; public DJSet(int n) { upper = new int[n]; Arrays.fill(upper, -1); } public int root(int x) { return upper[x] < 0 ? x : (upper[x] = root(upper[x])); } public boolean equiv(int x, int y) { return root(x) == root(y); } public boolean union(int x, int y) { x = root(x); y = root(y); if (x != y) { if (upper[y] < upper[x]) { int d = x; x = y; y = d; } upper[x] += upper[y]; upper[y] = x; } return x == y; } public int count() { int ct = 0; for (int u : upper) if (u < 0) ct++; return ct; } } public static int[][] parents3(int[][] g, int root) { int n = g.length; int[] par = new int[n]; Arrays.fill(par, -1); int[] depth = new int[n]; depth[0] = 0; int[] q = new int[n]; q[0] = root; for (int p = 0, r = 1; p < r; p++) { int cur = q[p]; for (int nex : g[cur]) { if (par[cur] != nex) { q[r++] = nex; par[nex] = cur; depth[nex] = depth[cur] + 1; } } } return new int[][] { par, q, depth }; } public static int[][] parentToG(int[] par) { int n = par.length; int[] ct = new int[n]; for(int i = 0;i < n;i++){ if(par[i] >= 0){ ct[i]++; ct[par[i]]++; } } int[][] g = new int[n][]; for(int i = 0;i < n;i++){ g[i] = new int[ct[i]]; } for(int i = 0;i < n;i++){ if(par[i] >= 0){ g[par[i]][--ct[par[i]]] = i; g[i][--ct[i]] = par[i]; } } return g; } public static int[] enumPrevWall(int[] a) { int n = a.length; int[] L = new int[n]; L[0] = -1; for(int i = 1;i < n;i++){ L[i] = i-1; while(L[i] >= 0 && a[L[i]] < a[i])L[i] = L[L[i]]; } return L; } public static int[] enumPrevShutter(int[] a) { int n = a.length; int[] L = new int[n]; L[0] = -1; for(int i = 1;i < n;i++){ L[i] = i-1; while(L[i] >= 0 && a[L[i]] > a[i])L[i] = L[L[i]]; } return L; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new E2().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }