E题的第二种解法。 修改转成查询用线段树维护每个位置左端位置和右端位置可以变成 q*logn。 大于sqrt(2w)的质数可以用莫队。  这样不是随机的也一样。 复杂度是O(q*logn + q*34*logn + (q+n)*sqrt(n))。