B - Arithmetic Progression Subsequence
Source: atcoder
Difficulty: 500

Problem Statement
You are given a sequence
A
of length
N
consisting of integers between
1
and
\textbf{10}
, inclusive.
A pair of integers
(l,r)
satisfying
1\leq l \leq r\leq N
is called a good pair if it satisfies the following condition:
The sequence
(A_l,A_{l+1},\ldots,A_r)
contains a (possibly non-contiguous) arithmetic subsequence of length
3
. More precisely, there is a triple of integers
(i,j,k)
with
l \leq i < j < k\leq r
such that
A_j - A_i = A_k - A_j
.
Find the number of good pairs.
Constraints
3 \leq N \leq  10^5
1\leq A_i \leq 10
All input numbers are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
\ldots
A_N
Output
Print the answer.
Sample Input 1
5
5 3 4 1 5
Sample Output 1
3
There are three good pairs:
(l,r)=(1,4),(1,5),(2,5)
.
For example, the sequence
(A_1,A_2,A_3,A_4)
contains an arithmetic subsequence of length
3
, which is
(5,3,1)
, so
(1,4)
is a good pair.
Sample Input 2
3
1 2 1
Sample Output 2
0
There may be cases where no good pairs exist.
Sample Input 3
9
10 10 1 3 3 7 2 2 5
Sample Output 3
3

C++ solution:
#include<bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define nl "\n"
#define int ll
typedef long long ll;
typedef long double ld;
using namespace std;

const int N = 200200;
const int mod = 1e18;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
	vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= 1;
    }
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int j = i;
		vector<int> bad(10, 0);
		while (j < n && !bad[a[j]]) {
			for (int k = i; k < j; k++) {
				int x = 2 * a[j] - a[k];
				if (x >= 0 && x < bad.size()) bad[x] = 1;
			}
			j += 1;
		}
		ans += (n - j);
	}
	cout << ans << nl;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

const (
	inf = 1 << 60
	MOD = 998244353
)

func main() {
	/*** INIT ***/
	defer wt.Flush()
	sc.Buffer([]byte{}, inf)
	sc.Split(bufio.ScanWords)

	n := InputInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = InputInt()
		a[i]--
	}

	ans := 0
	for i := 0; i < n-2; i++ {
		count, waiting := make([]int, 10), make([]bool, 10)
		count[a[i]]++
		flag := false
		for j := i + 1; j < Min(n, i+20); j++ {
			if waiting[a[j]] == true {
				ans += n - j
				flag = true
				break
			}
			count[a[j]]++
			if count[a[j]] == 2 {
				waiting[a[j]] = true
			}
			if 1 <= count[a[j]] {
				for d := 1; d <= 4; d++ {
					if 0 <= a[j]-d && count[a[j]-d] != 0 && a[j]+d < 10 {
						waiting[a[j]+d] = true
					}
					if a[j]+d < 10 && count[a[j]+d] != 0 && 0 <= a[j]-d {
						waiting[a[j]-d] = true
					}
				}
			}
		}
		if flag == false {
			ans += n - Min(n, i+20)
		}
	}
	OutInt(ans)
}

func Min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

/*** I/O ***/
func InputInt() int {
	sc.Scan()
	val, _ := strconv.Atoi(sc.Text())
	return val
}

func InputString() string {
	sc.Scan()
	return sc.Text()
}

func OutInt(val int) {
	fmt.Fprintln(wt, val)
}

func OutString(s string) {
	fmt.Fprintln(wt, s)
}

Java solution:
import java.util.function.BinaryOperator;
import java.util.InputMismatchException;
import java.util.TreeSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.io.FileInputStream;
import java.util.Comparator;
import java.util.function.Function;
import java.io.PrintWriter;
import java.util.Objects;
import java.io.InputStream;
import java.io.IOException;

public class Main {
    InputStream is;

    static int __t__ = 1;
    static int __f__ = 0;
    static int __FILE_DEBUG_FLAG__ = __f__;
    static String __DEBUG_FILE_NAME__ = "src/main/java/test/sample-1.in";

    FastScanner in;
    PrintWriter out;

    public void solve() {
        int n = in.nextInt();
        int[] a = in.nextIntArray(n);
        int m = 21;
        long res = (n * (n - 1L)) / 2L;

        boolean[][] dp = new boolean[n][m];
        for (int d = 1; d < m; d++) {
            for (int l = 0; l < n - d; l++) {
                int r = l + d;
                boolean ok = false;
                for (int s = l + 1; s < r; s++) {
                    if (a[s] - a[l] == a[r] - a[s]) {
                        ok = true;
                        break;
                    }
                }
                dp[l][d] = ok | dp[l][d - 1] | dp[l + 1][d - 1];
                if (!dp[l][d]) {
                    res--;
                }
            }
        }
        System.out.println(res);
    }

    public void run() {
        if (__FILE_DEBUG_FLAG__ == __t__) {
            try {
                is = new FileInputStream(__DEBUG_FILE_NAME__);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
            System.out.println("FILE_INPUT!");
        } else {
            is = System.in;
        }
        in = new FastScanner(is);
        out = new PrintWriter(System.out);

        solve();
    }

    public static void main(final String[] args) {
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("--with-file")) {
                Main.__FILE_DEBUG_FLAG__ = __t__;
            }
        }
        new Main().run();
    }
}

class ModCombination {
    private final ModLib modLib;

    private final long[] fact;
    private final long[] invfact;

    private ModCombination(ModLib modLib, long[] fact, long[] invfact) {
        this.modLib = modLib;
        this.fact = fact;
        this.invfact = invfact;
    }

    public static ModCombination create(int size, ModLib modLib) {
        long[] fact = new long[size];
        fact[0] = 1;
        for (int i = 0; i < size - 1; i++) {
            fact[i+1] = modLib.mult(fact[i], i + 1);
        }
        long[] invfact = new long[size];
        invfact[size-1] = modLib.div(1, fact[size-1]);
        for (int i = size - 2; i >= 0; i--) {
            invfact[i] = modLib.mult(invfact[i+1], i + 1);
        }
        return new ModCombination(modLib, fact, invfact);
    }

    public long fact(int x) {
        return fact[x];
    }

    public long invfact(int x) {
        return invfact[x];
    }

    public long permutation(int a, int b) {
        if (b > a) {
            return 0;
        }
        return modLib.mult(fact[a], invfact[a-b]);
    }

    public long comb(int a, int b) {
        if (a == 0) {
            return 1;
        }
        if (b > a) {
            return 0;
        }
        return modLib.mult(fact[a], modLib.mult(invfact[b], invfact[a-b]));
    }
}


class ModLib {
    final long mod;

    public ModLib(long mod) {
        this.mod = mod;
    }

    public static ModLib m998244353() {
        return new ModLib(998244353);
    }

    public static ModLib m1000000007() {
        return new ModLib(1000000007);
    }

    public long add(long a, long b) {
        return (a + b) % mod;
    }

    public long sub(long a, long b) {
        return (a - b + mod) % mod;
    }

    public long mult(long a, long b) {
        return (a * b) % mod;
    }

    public long pow(long a, long x) {
        long res = 1;
        for ( ; x > 0; x >>= 1) {
            if (x % 2 == 1) res = mult(res, a);
            a = mult(a, a);
        }

        return res;
    }

    public long div(long a, long b) {
        return mult(a, pow(b % mod, mod - 2));
    }
}

class Preconditions {
    public static void check(boolean x) {
        check(x, "");
    }

    public static void check(boolean x, String message) {
        if (!x) {
            throw new IllegalArgumentException(message);
        }
    }

}


class Multiset<T> extends java.util.TreeMap<T, Long> {
    int count;

    public Multiset() {
        super();
        count = 0;
    }

    public Multiset(java.util.List<T> list) {
        super();
        for (T e : list) this.addOne(e);
    }

    public int countAll() {
        return count;
    }

    public void add(T elm, long amount) {
        if (!this.containsKey(elm)) {
            put(elm, amount);
        } else {
            long v = get(elm) + amount;
            if (v == 0) {
                remove(elm);
            } else {
                put(elm, v);
            }
        }
        count += amount;
    }

    public void addOne(T elm) {
        this.add(elm, 1);
    }

    public void removeOne(T elm) {
        this.add(elm, -1);
    }

    public void removeAll(T elm) {
        this.add(elm, -getOrDefault(elm, 0L));
    }

    public static <T> Multiset<T> merge(Multiset<T> a, Multiset<T> b) {
        Multiset<T> c = new Multiset<>();
        for (T x : a.keySet()) c.add(x, a.getOrDefault(x, 0L));
        for (T y : b.keySet()) c.add(y, b.getOrDefault(y, 0L));
        return c;
    }
}


class Sets {
    public static <E> Set<E> of(E... es) {
        return new HashSet<>(Arrays.asList(es));
    }

    public static <E> Set<E> intersect(Set<E> s1, Set<E> s2) {
        final Set<E> res = new HashSet<>();
        res.addAll(s1.stream().filter(s2::contains).collect(Collectors.toList()));
        res.addAll(s2.stream().filter(s1::contains).collect(Collectors.toList()));
        return res;
    }
}


class Pair<A, B> {
    public final A a;
    public final B b;

    public Pair(A a, B b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "a=" + a +
                ", b=" + b +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair<?, ?> pair = (Pair<?, ?>) o;
        return Objects.equals(a, pair.a) && Objects.equals(b, pair.b);
    }

    @Override
    public int hashCode() {
        return Objects.hash(a, b);
    }
}


class Operators {
    public static <T> BinaryOperator<T> compareAndChoose(Function<T, Double> f) {
        return (t1, t2) -> f.apply(t1) < f.apply(t2) ? t1 : t2;
    }
}


class FastScanner {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream) {
        this.stream = stream;
        // stream = new FileInputStream(new File("dec.in"));
    }

    int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public boolean isEndline(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public int[] nextIntArray(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = nextInt();

        return array;
    }

    public int[][] nextIntMap(int n, int m) {
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = nextIntArray(m);
        }
        return map;
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public long[] nextLongArray(int n) {
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = nextLong();

        return array;
    }

    public long[][] nextLongMap(int n, int m) {
        long[][] map = new long[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = nextLongArray(m);
        }
        return map;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public double[] nextDoubleArray(int n) {
        double[] array = new double[n];
        for (int i = 0; i < n; i++)
            array[i] = nextDouble();

        return array;
    }

    public double[][] nextDoubleMap(int n, int m) {
        double[][] map = new double[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = nextDoubleArray(m);
        }
        return map;
    }

    public String next() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public String[] nextStringArray(int n) {
        String[] array = new String[n];
        for (int i = 0; i < n; i++)
            array[i] = next();

        return array;
    }

    public String nextLine() {
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndline(c));
        return res.toString();
    }

    public int[][] nextPackedIntArrays(int packN, int size) {
        int[][] res = new int[packN][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < packN; j++) {
                res[j][i] = nextInt();
            }
        }
        return res;
    }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

function lowerBound(ary,v,l=0,r=ary.length){--l;for(var c;1<r-l;)ary[c=l+r>>1]<v?l=c:r=c;return r;}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var n = next();
  var a = nexts(n);
  var b = xArray("[]",10);
  for(var i = 0; i < n; i++){
    a[i]--;
    b[a[i]].push(i);
  }
  var p = [];
  for(var i = 0; i < n; i++){
    var t = (9-a[i])>>1;
    var mn = 1e9;
    for(var j = 0-(a[i]>>1); j <= t; j++){
      var y = a[i]+j, z = y+j;
      var l=lowerBound(b[y],i+1);
      if(l === b[y].length)continue;
      var r=lowerBound(b[z],b[y][l]+1);
      if(r === b[z].length)continue;
      mn = Math.min(mn, b[z][r]);
    }
    if(mn === 1e9)continue;
    p.push([i,mn]);
  }
  p.sort((a,b)=>a[1]!==b[1]?a[1]-b[1]:a[0]-b[0]);
  var l = -1, r = -1, ans = 0;
  for(var i = 0; i < p.length; i++){
    var [x,y] = p[i];
    if(x <= l)continue;
    ans += (n-y) * (x-l);
    r = y;
    l = x;
  }
  return ans;
}

Python solution:
def ii(): return int(input())
def ist(): return input().split()
def mi(): return map(int,input().split())
def lmi(): return list(map(int,input().split()))
inf = float("inf")
def answer(s):
  print(s)
  exit()
################################################
n = ii()
a = lmi()

r_index = [inf]*n
c_index = [-1]*10
l_index = [[-1]*10]
for ai,aa in enumerate(a):
  for ci,cc in enumerate(c_index):
    if cc > 0:
      l = (ci+1)*2 - aa
      if 0<l<=10:
        li = l_index[cc][(ci+1)*2-aa-1]
        if li >= 0:
          r_index[li] = min(r_index[li],ai)
  c_index[aa-1] = ai
  l_index.append(c_index.copy())
mn = inf
for i in range(n-1,-1,-1):
  mn = min(mn,r_index[i])
  r_index[i] = mn
i = 0
ans = 0
while r_index[i] != inf:
  ans += n-r_index[i]
  i += 1
print(ans)

Ruby solution:
n = gets.to_i
a = gets.split.map(&:to_i)
ans = 0
first = Array.new(11,-1)
second = Array.new(11,-1)
last = 0
for i in 0...n
    if second[a[i]] != -1
        if second[a[i]] >= last
            ans += (n-i) * (second[a[i]] - last + 1)
            last = second[a[i]] + 1
        end
    end
    for j in 0...11
        next if first[j] == -1
        next if a[i] + (a[i] - j) < 1 || a[i] + (a[i] - j) > 10
        second[a[i] + (a[i] - j)] = [second[a[i] + (a[i] - j)], first[j]].max
    end
    first[a[i]] = i
end
puts ans