{"raw_statement":[{"iden":"problem statement","content":"We have $N$ colored balls arranged in a row from left to right; the color of the $i$\\-th ball from the left is $c_i$.\nYou are given $Q$ queries. The $i$\\-th query is as follows: how many different colors do the $l_i$\\-th through $r_i$\\-th balls from the left have?"},{"iden":"constraints","content":"*   $1\\leq N,Q \\leq 5 \\times 10^5$\n*   $1\\leq c_i \\leq N$\n*   $1\\leq l_i \\leq r_i \\leq N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$c_1$ $c_2$ $\\cdots$ $c_N$\n$l_1$ $r_1$\n$l_2$ $r_2$\n$:$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"4 3\n1 2 1 3\n1 3\n2 4\n3 3"},{"iden":"sample output 1","content":"2\n3\n1\n\n*   The $1$\\-st, $2$\\-nd, and $3$\\-rd balls from the left have the colors $1$, $2$, and $1$ - two different colors.\n*   The $2$\\-st, $3$\\-rd, and $4$\\-th balls from the left have the colors $2$, $1$, and $3$ - three different colors.\n*   The $3$\\-rd ball from the left has the color $1$ - just one color."},{"iden":"sample input 2","content":"10 10\n2 5 6 5 2 1 7 9 7 2\n5 5\n2 4\n6 7\n2 2\n7 8\n7 9\n1 8\n6 9\n8 10\n6 8"},{"iden":"sample output 2","content":"1\n2\n2\n1\n2\n2\n6\n3\n3\n3"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}