AT_abc293_g [ABC293G] Triple Index

[problemUrl]: https://atcoder.jp/contests/abc293/tasks/abc293_g 長さ $ N $ の正整数列 $ (A_1,\ A_2,\ \ldots,\ A_N) $ と、この数列に関する $ Q $ 個のクエリが与えられます。 $ q\ =\ 1,\ 2,\ \ldots,\ Q $ のそれぞれについて、$ q $ 番目のクエリでは整数の $ 2 $ つ組 $ (l_q,\ r_q) $ が与えられるので、 下記の $ 2 $ つの条件をともに満たす整数の $ 3 $ つ組 $ (i,\ j,\ k) $ の個数を出力してください。 - $ l_q\ \leq\ i\ \lt\ j\ \lt\ k\ \leq\ r_q $ - $ A_i\ =\ A_j\ =\ A_k $

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_Q $ $ r_Q $

$ Q $ 行出力せよ。 $ q\ =\ 1,\ 2,\ \ldots,\ Q $ について、$ q $ 行目には $ q $ 番目のクエリに対する答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ l_q\ \leq\ r_q\ \leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて、問題文中の $ 2 $ つの条件をともに満たす整数の $ 3 $ つ組 $ (i,\ j,\ k) $ は、 $ (1,\ 5,\ 9),\ (4,\ 6,\ 8),\ (4,\ 6,\ 10),\ (4,\ 8,\ 10),\ (6,\ 8,\ 10) $ の $ 5 $ 個です。