U526833 I 数组喜欢数字(Hard)

fang_baby有一个长度为 $n$ 的有序数组，他有 $q$ 个询问，对于每一个询问，他想知道一个数字 $a$ 能插在这个数组的什么区间。例如一个数组A[2,3,3,4],如果fang_baby想插入一个数字3,那么这个数字可能出现在A[2,**3**,3,3,4], A[2,3,**3**,3,4],A[2,3,3,**3**,4],即为区间[2,4]。 在这个版本中，每个询问都需要对数组进行一次更新，即每次询问过后都会将数字插入数组。 题目保证给定的数组为升序数组。

第一行给定两个正整数 $n$ ， $q$ 分别表示数组长度与询问个数。( $1

输出 $q$ 行，每一行输出两个由空格隔开的正整数表示能插入的位置。