Descripción

OCI-Cub está jugando en una playa de arena. Hace un castillo de arena. El castillo de arena hecho por OCI-Cubo está contenido en una región rectangular en la playa de arena. La región rectangular consta de celdas de ~H~ filas horizontales y W columnas verticales. La celda en la fila i-ésima (~1 \le i \le H~) desde el norte y la columna j-ésima (~1 \le j \le W~) desde el oeste tiene altura ~A_{i, j}~. Obsérvese que los valores de ~A_{i, j}~ son diferentes entre sí.

Para el castillo de arena, OCI-Cub realizó las siguientes acciones.

1. En primer lugar, OCI-Cub eligió una celda, y comenzó a moverse desde la celda elegida.

2. A continuación, se movió desde la celda actual a una celda adyacente en una de las cuatro direcciones. Tiene que moverse a una celda que esté más abajo que la celda actual. Repitió esto cero o más veces.

Por último, si vemos las celdas que ha visitado desde arriba, las celdas forman un rectángulo.

Tarea

Dada la información de la altura ~A_{i, j}~ de cada celda, escribe un programa que calcule el número de rectángulos posibles formados por las celdas visitadas por OCI-Cub.

Entrada

Lea los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

~H~ ~W~

~A_{1,1}~ ~A_{1,2}~ --- ~A_{1,W}~

~A_{2,1}~ ~A_{2,2}~ --- ~A_{2,W}~

.

.

.

~A_{H,1}~ ~A_{H,2} --- ~A_{H,W}~

Salida

Escriba una línea en la salida estándar. La salida debe contener el número de posibles rectángulos formados por las celdas visitadas por OCI-Cub.

Restricciones

• ~H \ge 1~.
• ~W \ge 1~.
• ~H~ × ~W \le 50 000~.
• ~1 \le A_{i, j} \le 10 000 000~ (~1 \le i \le H, 1 \le j = W~).
• ~A_{i1, j1}~ ≠ ~A_{i2, j2}~ (~1 \le i_1 \le H~, ~1 \le j_1 \le W~, ~1 \le i_2 \le H~, ~1 \le j_2 \le W~, ~(i_1, j_1)~ ≠ ~(i_2, j_2~)).

Subtareas

1. (9 puntos) ~H~ = ~1~.
2. (10 puntos) ~H~ × ~W \le 100~.
3. (5 puntos) ~H~ × ~W \le 1 500~.
4. (56 puntos) ~H~ × ~W \le 7 000~.
5. (20 puntos) Sin restricciones adicionales.

Ejemplo de entrada y salida

Ejemplo de Entrada #1

1 5
2 4 7 1 5

Ejemplo de Salida #1

10

Dado que hay ~10~ rectángulos posibles formados por las celdas visitadas por OCI-Cub, salida ~10~

Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Ejemplo de Entrada #2

3 2
18 10
19 12
17 13

Ejemplo de Salida #2

15

Como hay ~15~ rectángulos posibles formados por las celdas visitadas por JOI-kun, salida ~15~

Esta entrada de ejemplo satisface las restricciones de las subtareas 2, 3, 4, 5.

Ejemplo de Entrada #3

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

Ejemplo de Salida #3

65

Por ejemplo, los siguientes rectángulos pueden estar formados por las celdas visitadas por OCI-Cub. Como hay ~65~ rectángulos posibles en total, salida ~65~.

Este ejemplo de entrada satisface las restricciones de las subtareas 2, 3, 4, 5.