Дадена ви е долга низа од N обоени жетони. Заради едноставност, различните бои се претставени со различен позитивен цел број. Така, секој елемент од низата A₁, A₂,…, A_N ја претставува бојата на соодветниот жетон.

Се поставува прашањето, на колку различни начини можеме да избереме 3 жетони со иста боја од горната низа. За да биде поинтересно, во оваа задача ќе ви поставиме Q прашанки, и секоја прашанка ќе каже за кој опсег во низата не интересира горното прашање.

Формално, за секое q = 1, 2, …, Q, q-тата прашанка ви дава два броја l_q и r_q, а вие треба да го отпечатите бројот на целобројни тројки (i, j, k) такви што l_q ≤ i < j < k ≤ r_q​, и A_i​ = A_j ​= A_k​.

Влез

Во првиот ред од влезот се дадени целите броеви N (1 ≤ N ≤ 2×10⁵) и Q (1 ≤ Q ≤ 2×10⁵).
Во вториот ред се дадени N цели броеви, елементите на низата А (1 ≤ A_i​ ​≤ 2×10⁵).
Во следните Q редови се дадени по два цели броја, l_q​ ​и r_q​ (1 ≤ l_q​ ​≤ r_q​ ​≤ N) кои ја опишуваат q-тата прашанка.

Забелешка.
Во подзадача 1, за 18 поени: Q ≤ 100
Во подзадача 2, за 20 поени: 1 ≤ A_i ≤ 1000

Излез

Отпечатете во Q редови по еден цел број - одговорот на секоја од прашанките.

Ограничувања

Временско ограничување: 700 milliseconds
Мемориско ограничување: 512 megabytes

Примери

влез
10 5
1 5 1 1 2 1 2 5 2 8
1 4
1 6
5 9
1 10
4 8

излез
1
4
1
5
0

Објаснување на примерот:
Во прашанката (1, 4) тројки се: (1, 3, 4)
Во прашанката (1, 6) тројки се: (1, 3, 4), (1, 3, 6), (1, 4, 6), (3, 4, 6)
Во прашанката (5, 9) тројки се: (5, 7, 9)
Во прашанката (1, 10) тројки се: (1, 3, 4), (1, 3, 6), (1, 4, 6), (3, 4, 6), (5, 7, 9)
Во прашанката (4, 8) нема тројки.