Como las performances son distintas, cada subarreglo improvementous se puede mapear de forma única al índice de su valor mínimo o máximo.

Supongamos que fijamos la ubicación de nuestro valor mínimo, y contamos la cantidad de subarreglos válidos correspondientes. Una forma posible de contar los subarreglos es fijar el extremo izquierdo, y contar todos los extremos derechos válidos. ¿Cómo podemos reducir la cantidad de extremos izquierdos que consideramos?

Explicación

Como se mencionó en las pistas, iteramos sobre $i$, y contamos todos los subarreglos donde la ubicación $i$ tiene el valor mínimo. Sean $l_i$ y $r_i$ las posiciones más cercanas a la izquierda y a la derecha de $i$ que contienen valores menores que $i$. Los extremos de cualquier subarreglo válido no pueden cruzar $l_i$ ni $r_i$.

Un método naive para calcular nuestra respuesta sería iterar sobre nuestro extremo izquierdo y contar los extremos derechos válidos. Si nuestro extremo izquierdo es $x$, entonces la cantidad de extremos derechos válidos es $\max(0, r - y)$, si $y$ es el primer índice después de $i$ tal que $a[y] > \max_{x \le j \le i} a[j]$.

Una optimización que podemos hacer es observar que todos los índices $x$ donde $\max_{x \le j \le i} a[j]$ es el mismo corresponden al mismo rango de extremos derechos válidos. Así, podemos comprimir nuestros extremos izquierdos.

Con esa optimización, la cantidad de extremos izquierdos relevantes a lo largo de todos los $i$ se amortiza a $\mathcal{O}(n)$. Para entender por qué, consideremos las siguientes observaciones verdaderas:

• Todos los extremos izquierdos válidos necesitan que su valor esté en el rango $[l_i + 1, i]$.
• Para todas las posiciones $j$ en $[i + 1, r - 1]$, $l_j \geq i$, ya que $a_i$ está garantizado a ser menor que $a_j$. Así, los mismos extremos izquierdos válidos para $i$ no pueden aplicarse a índices en este rango.
• Si un extremo izquierdo válido tiene extremos derechos válidos, entonces el valor mayor más cercano debe estar dentro de $[i + 1, r - 1]$. Si tal valor no existe, no lo consideramos.
• Para índices en $r$ o después, cualquier extremo izquierdo considerado en $i$ es irrelevante, ya que la existencia de un valor mayor en el rango $[i + 1, r - 1]$ significa que ya no lo consideramos.

Así, lo que resta es hallar eficientemente los extremos izquierdos relevantes y contar la cantidad de extremos derechos correspondientes. Para cada $i$, calculamos la ubicación del elemento mayor más cercano a su izquierda y a su derecha.

Hallar todos los extremos izquierdos relevantes para un índice $i$ se puede hacer empezando en $i$, y encadenando al siguiente elemento mayor a la izquierda hasta que salgamos de nuestro rango de extremos izquierdos posibles.

Que un extremo izquierdo sea relevante implica que el elemento mayor más cercano a la derecha está después del índice $i$. Así, si tal elemento está en el rango $[i + 1, r - 1]$, entonces podemos contar fácilmente la cantidad de extremos derechos. En caso contrario, dejamos de iterar.

Para calcular los elementos mayor y menor más cercanos, usamos una pila monótona.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <bits/stdc++.h>
 
using ll = long long;
 
ll conta(int n, std::vector<int> a) {
	// calcula el elemento mayor más cercano, y mete idx en la pila
	const auto nearest_bigger = [&](std::vector<int> &stk, int idx) -> int {
		while (stk.size() > 1 && a[stk.back()] < a[idx]) { stk.pop_back(); }
 
		int res = stk.back();
		stk.push_back(idx);
		return res;
	};
 
	// calcula el elemento menor más cercano, y mete idx en la pila
	const auto nearest_smaller = [&](std::vector<int> &stk, int idx) -> int {
		while (stk.size() > 1 && a[stk.back()] > a[idx]) { stk.pop_back(); }
 
		int res = stk.back();
		stk.push_back(idx);
		return res;
	};
 
	// calculamos los elementos mayor y menor más cercanos a la izquierda para cada índice
	std::vector<int> stk_b{-1}, stk_s{-1};
	std::vector<int> big_l(n), small_l(n);
	for (int i = 0; i < n; i++) {
		big_l[i] = nearest_bigger(stk_b, i);
		small_l[i] = nearest_smaller(stk_s, i);
	}
 
	// calculamos los elementos mayor y menor más cercanos a la derecha para cada índice
	stk_b = stk_s = {n};
	std::vector<int> big_r(n), small_r(n);
	for (int i = n - 1; i >= 0; i--) {
		big_r[i] = nearest_bigger(stk_b, i);
		small_r[i] = nearest_smaller(stk_s, i);
	}
 
	ll res = 0;
	for (int i = 0; i < n; i++) {
		// contamos los subarreglos 'improvementous' para los que i es el mínimo
		int lb = small_l[i] + 1;
		int rb = small_r[i] - 1;
 
		// iteramos sobre cada máximo relevante (p. ej. max(a[j]...i) siendo útil), y
		// contamos la cantidad de subarreglos posibles para este máximo
		int idx = i;
		while (big_l[idx] >= lb) {
			// dejamos de iterar si este máximo es demasiado grande para el rango [lb, rb]
			if (big_r[idx] > rb) break;
 
			// como nuestro índice es un máximo relevante, sabemos que el elemento
			// mayor más cercano a la derecha NO está en el rango [idx, i]
			res += 1ll * (idx - big_l[idx]) * (rb - big_r[idx] + 1);
			idx = big_l[idx];
		}
 
		// sumamos el resultado para todos los extremos izquierdos restantes
		if (big_r[idx] <= rb) { res += 1ll * (idx - lb + 1) * (rb - big_r[idx] + 1); }
	}
 
	return res;
}