在线计数排名

难度：T4

【知识点：频率前缀】

前置知识：树状数组、重复值计数。

题目描述与输入

首行 $M,q$，集合初始为空。随后$q$行：1 x 插入值$x$（可重复）；2 x 查询严格小于$x$的元素个数。

输出格式

每个查询输出一行数量。

数据范围

$1\le M\le1000$，$1\le q\le2000$，$1\le x\le M$。

样例输入

5 5
1 2
1 2
1 5
2 2
2 5

样例输出

0
2

样例解释

插入$2$、$2$、$5$后，小于$2$有$0$个，小于$5$有$2$个。