F - Double Sum 3
Source: atcoder
Difficulty: 525

Problem Statement
You are given an integer sequence
A=(A_1,A_2,\ldots,A_N)
of length
N
.
For each integer pair
(L,R)
with
1 \le L \le R \le N
, define
f(L,R)
as follows:
Start with an empty blackboard. Write the
R-L+1
integers
A_L, A_{L+1}, \ldots, A_R
on the blackboard in order.
Repeat the following operation until all integers on the blackboard are erased:
Choose integers
l, r
with
l \le r
such that every integer from
l
through
r
appears at least once on the blackboard. Then, erase all integers from
l
through
r
that are on the blackboard.
Let
f(L,R)
be the minimum number of such operations needed to erase all the integers from the blackboard.
Find
\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R)
.
Constraints
1 \le N \le 3 \times 10^5
1 \le A_i \le N
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\ldots
A_N
Output
Print the answer.
Sample Input 1
4
1 3 1 4
Sample Output 1
16
For example, in the case of
(L,R)=(1,4)
:
The blackboard has
1,3,1,4
.
Choose
(l,r)=(1,1)
and erase all occurrences of
1
. The blackboard now has
3,4
.
Choose
(l,r)=(3,4)
and erase all occurrences of
3
and
4
. The blackboard becomes empty.
It cannot be done in fewer than two operations, so
f(1,4) = 2
.
Similarly, you can find
f(2,4)=2
,
f(1,1)=1
, etc.
\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16
, so print
16
.
Sample Input 2
5
3 1 4 2 4
Sample Output 2
23
Sample Input 3
10
5 1 10 9 2 5 6 9 1 6
Sample Output 3
129

C++ solution:
#include <bits/extc++.h>
using namespace std;

#define FastIO
#ifdef FastIO
struct IOStream
{
    static constexpr int INBUF = 1 << 21 | 1,OUTBUF = 1 << 21 | 1;
    char ibuf[INBUF],obuf[OUTBUF],ostk[50],otop,*ip1,*ip2,*op;
    #ifndef LOCAL
    #define getchar() (ip1 == ip2 && (ip2 = (ip1 = ibuf) + fread(ibuf,1,INBUF,stdin),ip1 == ip2) ? EOF : *ip1++)
    #define flush() (fwrite(obuf,1,op - obuf,stdout),op = obuf)
    #define putchar(ch) ((op == (obuf + OUTBUF) && flush()),*op++ = (ch))
    #else
    #define flush()
    #endif
    IOStream()
    {ip1 = ip2 = ibuf,op = obuf,otop = 0;}
    ~IOStream()
    {flush();}
    #define Read(T) inline IOStream& operator>>(T& x){x = 0;char ch = getchar();while(!isdigit(ch)) ch = getchar();while(isdigit(ch)){x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return *this;}
    Read(unsigned short)
    Read(unsigned int)
    Read(unsigned long long)
    Read(__uint128_t)
    #undef Read
    #define Read(T) inline IOStream& operator>>(T& x){x = 0;char ch = getchar(),f = 0;while(!isdigit(ch)){f |= (ch == '-');ch = getchar();}while(isdigit(ch)){x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}x = (f ? -x : x);return *this;}
    Read(short)
    Read(int)
    Read(long long)
    Read(__int128_t)
    #undef Read
    #define Write(T) inline IOStream& operator<<(T x){do{ostk[otop++] = x % 10;x /= 10;}while(x);while(otop)putchar(ostk[--otop] ^ 48);return *this;}
    Write(unsigned short)
    Write(unsigned int)
    Write(unsigned long long)
    Write(__uint128_t)
    #undef Write
    #define Write(T) inline IOStream& operator<<(T x){if(x < 0)putchar('-'),x = -x;do{ostk[otop++] = x % 10;x /= 10;}while(x);while(otop)putchar(ostk[--otop] ^ 48);return *this;}
    Write(short)
    Write(int)
    Write(long long)
    Write(__int128_t)
    #undef Write
    inline IOStream& operator>>(char &ch){do ch = getchar();while(!isalnum(ch));return *this;}
    inline IOStream& operator>>(string& s){char ch = getchar();while(!isalnum(ch))ch = getchar();while(isalnum(ch)){s += ch;ch = getchar();}return *this;}
    inline IOStream& operator<<(const char* s){for(int i = 0;s[i] != '\0';i++)putchar(s[i]);return *this;}
    inline IOStream& operator<<(char c){putchar(c);return *this;}
    inline IOStream& operator<<(string s){for(int i = 0;i < s.length();i++)putchar(s[i]);return *this;}
}IO;
#define cin IO
#define cout IO
#endif
#define int long long 

constexpr int MAXN = 3e5 + 5;
int n,a[MAXN],lst[MAXN],ans,f;
signed main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        int x = lst[a[i] - 1],y = lst[a[i]],z = lst[a[i] + 1];
        int IE = x + y + z - min(x,y) - min(y,z) - min(x,z) + min(min(x,y),z);
        f += i - IE - min(x,z) + min(min(x,y),z);
        ans += f;
        lst[a[i]] = i;
    }
    cout << ans;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func main() { solve(os.Stdin, os.Stdout) }

func solve(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	n := readNum(in)
	a := readNNums(in, n)
	idxs := make([][]int, n+1)
	for i, v := range a {
		idxs[v] = append(idxs[v], i)
	}

	ans := 0
	for i := 1; i <= n; i++ {
		pre, pi := -1, 0
		for _, j := range idxs[i] {
			nxt := n
			for pi < len(idxs[i-1]) && idxs[i-1][pi] < j {
				pi++
			}
			if pi < len(idxs[i-1]) {
				nxt = idxs[i-1][pi]
			}
			if pi > 0 {
				pre = max(pre, idxs[i-1][pi-1])
			}
			ans += (j - pre) * (nxt - j)
			pre = j
		}
	}
	fmt.Fprintln(out, ans)
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.util.function.IntFunction;
import java.util.function.LongFunction;

public class Main {
	public static void main(String[] args) {
		Main o = new Main();
		o.solve();
	}

	public void solve() {
		FastScanner sc = new FastScanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			A[i] = sc.nextInt();
		}

		int[] li = new int[N + 2];
		// Arrays.fill(li, -1);
		long ans = 0;
		long cur = 0;
		for (int i = 1; i <= N; i++) {
			int li0 = li[A[i]];
			int li1 = li[A[i] - 1];
			int li2 = li[A[i] + 1];
			if ( li0 == 0 ) {
				if ( li1 > 0 && li2 > 0 ) {
					int m0 = Math.min(li1, li2);
					int m1 = Math.max(li1, li2);
					cur += m0 * (-1);
					cur += (i - m1);
				} else if ( li1 == 0 && li2 == 0 ) {
					cur += i;
				} else {
					int m0 = Math.max(li1, li2);
					cur += (i - m0);
				}
			} else {
				if ( li1 > li0 && li2 > li0 ) {
					int m0 = Math.min(li1, li2);
					int m1 = Math.max(li1, li2);
					cur += (m0 - li0) * (-1);
					cur += (i - m1);
				} else {
					int m0 = Math.max(Math.max(li0, li1), li2);
					cur += (i - m0);
				}
			}
			ans += cur;
			li[A[i]] = i;
		}

		System.out.println(ans);
	}

	static final char LF = '\n';
	static final char SPACE = ' ';
	static final String YES = "Yes";
	static final String NO = "No";
	void print(int[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void print(long[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void printYesNo(boolean yesno) {
		System.out.println(yesno ? YES : NO);
	}
	void printDouble(double val, int digit) {
		System.out.println(String.format("%." + digit + "f", val));
	}
	
	class FastScanner {
		private final InputStream in;
		private final byte[] buf = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		FastScanner( InputStream source ) { this.in = source; }
		private boolean hasNextByte() {
			if ( ptr < buflen ) return true;
			else {
				ptr = 0;
				try { buflen = in.read(buf); } catch (IOException e) { e.printStackTrace(); }
				if ( buflen <= 0 ) return false;
			}
			return true;
		} 
		private int readByte() { if ( hasNextByte() ) return buf[ptr++]; else return -1; } 
		private boolean isPrintableChar( int c ) { return 33 <= c && c <= 126; }
		private boolean isNumeric( int c ) { return '0' <= c && c <= '9'; }
		private void skipToNextPrintableChar() { while ( hasNextByte() && !isPrintableChar(buf[ptr]) ) ptr++; }
		public boolean hasNext() { skipToNextPrintableChar(); return hasNextByte(); }
		public String next() {
			if ( !hasNext() ) throw new NoSuchElementException();
			StringBuilder ret = new StringBuilder();
			int b = readByte();
			while ( isPrintableChar(b) ) { ret.appendCodePoint(b); b = readByte(); }
			return ret.toString();
		}
		public long nextLong() {
			if ( !hasNext() ) throw new NoSuchElementException();
			long ret = 0;
			int b = readByte();
			boolean negative = false;
			if ( b == '-' ) { negative = true; if ( hasNextByte() ) b = readByte(); }
			if ( !isNumeric(b) ) throw new NumberFormatException();
			while ( true ) {
				if ( isNumeric(b) ) ret = ret * 10 + b - '0';
				else if ( b == -1 || !isPrintableChar(b) ) return negative ? -ret : ret;
				else throw new NumberFormatException();
				b = readByte();
			}
		}
		public int nextInt() { return (int)nextLong(); }
		public double nextDouble() { return Double.parseDouble(next()); }
	}
}

JavaScript solution:
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map((x) => Number(x) - 1);
  const max = Array(N)
    .fill(0)
    .map(() => []);
  for (let i = 0; i < N; i++) max[A[i]].push(i);

  let ans = 0;
  for (let i = 0; i < N; i++) {
    let [l, r] = [0, N - 1];
    let res = lower_bound(max[A[i]], i);
    if (res > 0) l = max[A[i]][res - 1] + 1;
    if (res < max[A[i].length] - 1) r = max[A[i][res + 1]] - 1;

    let n = A[i] + 1;
    if (n < N && max[n].length !== 0) {
      let res = lower_bound(max[n], i);
      if (res !== 0) l = Math.max(l, max[n][res - 1] + 1);
    }

    if (n < N && max[n].length !== 0) {
      let res = lower_bound(max[n], i + 1);
      if (res !== max[n].length) r = Math.min(r, max[n][res] - 1);
    }

    ans += (i - l + 1) * (r - i + 1);
  }
  console.log(ans);
}
const isOK = (arr, mid, key) => arr[mid] >= key;
const lower_bound = (arr, key) => {
  let ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ok = arr.length; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ok - ng > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK(arr, mid, key)) ok = mid;
    else ng = mid;
  }
  return ok;
};

Main(require("fs").readFileSync(0, "utf8"));

Python solution:
N = int(input())
a = [*map(int, input().split())]
nearest = [N]*(N+1)
nearright = [N]*N
for n in range(N-1,-1,-1):
    nearright[n] = nearest[a[n]-1]
    nearest[a[n]] = n
ans = 0
nearest = [-1]*(N+1)
for n in range(N):
    ans += (n-max(nearest[a[n]-1],nearest[a[n]]))*(nearright[n]-n)
    nearest[a[n]] = n
print(ans)

Ruby solution:
eval"N,*A=1+"+`dd`.split*?,
r=[N]*N
q=b=[i=0]*N,*r.map{[]}
p A.map{|x|q[x]<<i+=1
q[x+1].reject!{r[_1]=i}
[i-[b[x],b[x-1]].max,b[x]=i]}.sum{_1.*r[_2]-_2}