L’invencible, sense por, sensual, misteriós, encantador, vigorós, diligent, aclaparador, magnífic, apassionat, bell i poderós emperador del país de les dues dimensions ha decidit construir la seva 168a residència en una ciutat que s’ha posat molt de moda recentment, la Ciutat Plana.

El procediment és senzill: escollirà una zona de la ciutat que s’ajusti als seus exquisits estàndards i rebrà com a “regal” tots els edificis d’aquesta zona per part de la seva lleial (i no recompensada) població.

Per descomptat, l’invencible, sense por, sensual, misteriós, encantador, vigorós, diligent, aclaparador, magnífic, apassionat, bell, poderós i "pacífic" emperador us ha encomanat (sense compensació econòmica, és clar) la tasca de comptar quantes zones compleixen els requisits per construir-hi la seva nova residència.

Entrada

Es rebran dos enters \(n\) i \(m\), indicant respectivament la mida de la ciutat i el nombre de restriccions. (\(0 < m \le n \le 200000\))

A continuació, la ciutat (fidel a la seva naturalesa bidimensional) es representarà mitjançant un vector d’enters \(x\) de mida \(n\), on cada element \(x_i\) indica el tipus d’edifici situat a la posició \(i\). (\(0 \le x_i \le 10^9\))

Finalment, es proporcionaran \(m\) parelles d’enters ("\(a_i b_i\)"), indicant que una zona vàlida ha de contenir com a mínim \(b_i\) edificis del tipus \(a_i\). (\(0 \le a_i \le 10^9\) i \(0 \le b_i \le n\))

Sortida

Mostra un únic enter: el nombre de zones (segments continus de \(x\)) que compleixen totes les condicions.

Tingues en compte que:

• Dues zones poden superposar-se parcialment.
• Una zona pot estar continguda dins d’una altra més gran.

Exemple d'entrada 1

5 1
1 2 1 3 1
1 2

Exemple de sortida 1

5

Explicació

Les zones (segments continus) que compleixen la condició (tenir com a mínim dos uns) són:

• Posicions 1–3 → [1 2 1]
• Posicions 1–4 → [1 2 1 3]
• Posicions 1–5 → [1 2 1 3 1]
• Posicions 2–5 → [2 1 3 1]
• Posicions 3–5 → [1 3 1]

Exemple d'entrada 2

6 2
1 2 1 3 2 1
1 2
2 1

Exemple de sortida 2

6

Explicació

Comproveu que hi ha 6 zones que compleixen la condició (tenir com a mínim dos uns i un dos).