$$$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

Given 3 permutations of equal lengths n ≤ 10⁵, let's call them A, B and C.
Find number of such i-s that there's no such j, that (A_i > A_j and B_i > B_j and C_i > C_j)

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?

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 x₁, x₂, x₃, ..., x_k is set of unique values from a_l, a_l + 1, a_l + 2, ..., a_r - 2, a_r - 1, a_r, then output x₁ xor x₂ xor x₃ xor ... xor x_k

1 ≤ n, q ≤ 10⁶
for all i, 1 ≤ a_i ≤ 10⁹

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

Problem was solved!

Input is consist of 1 ≤ q ≤ 2 * 10⁴ queries every of which are described with single positive integer n not exceeding 4 * 10⁶.
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 * 10⁶ and P_i for any i, 1 ≤ i ≤ 4 * 10⁶ 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.
Please, help me!