### deepwork's blog

By deepwork, history, 16 months ago, $a_1 = 1$
$a_2 = 5$
$a_n = a_{n-1} + n^2(a_{n-2}+1)$

Prove $a_n=(n+1)!-1$
P.S. Original problem By deepwork, history, 23 months ago, Given 3 permutations of equal lengths n ≤ 105, let's call them A, B and C.
Find number of such i-s that there's no such j, that (Ai > Aj and Bi > Bj and Ci > Cj)

By deepwork, history, 2 years ago, # Question is solved, please ignore this post

Why if xor sum of segment is equal to sum of segment, this condition is also satisfied for all subsegments of original segment?
I know that it's true when all bits in numbers are unique, but is it the only case when it's true, and if it is, then why? sum,
By deepwork, history, 2 years ago, Given an array of n positive integers called a
For each of q queries which are described with integers 1 ≤ l ≤ r ≤ n, output xor of unique values in segment(l, r), i.e. if x1, x2, x3, ..., xk is set of unique values from al, al + 1, al + 2, ..., ar - 2, ar - 1, ar, then output x1 xor x2 xor x3 xor ... xor xk

1 ≤ n, q ≤ 106
for all i, 1 ≤ ai ≤ 109

TL: 3.5 seconds
ML: 256 megabytes

How to solve it?
If it's possible, I'd like a solution which uses some of data structures listed below:
Segment Tree
Binary Rise/Lift
Trie
Merge Sort Tree xor,
By deepwork, history, 2 years ago, # Problem was solved!

Input is consist of 1 ≤ q ≤ 2 * 104 queries every of which are described with single positive integer n not exceeding 4 * 106.
Output is to print for each query: Where: x⌋ =  whole part of number, i.e. max integer which's  ≤ x
φ(x) is Euler Totient Function

OK, I can previously calculate phis of all numbers from 1 to 4 * 106 and Pi for any i, 1 ≤ i ≤ 4 * 106 in O(nlogn), but what's then? I don't know how to further optimize solution, because it is TLE with O(n) complexity per query. math, phi,