A long time ago in a galaxy far, far away, there were
A pair of planets
and are different planets- travelling between planet
and is possible using one or more interplanetary paths - binary XOR of the curiosity of all the paths in that travel is equal to 0
Alas, the times have changed and an evil emperor is ruling the galaxy. He decided to use the Force to destroy all the interplanetary paths in a certain order.
Determine the number of boring pairs of planets before the emperor started the destruction and after each destruction.
Input
The first line of input contains the integer
Each of the following
The following line of input contains the permutation of the first
Output
The output must contain
Scoring
In test cases worth 20% of total points, it will hold
In test cases worth at least 30% of total points, every path's curiosity will be equal to 0.
Sample Input 1
2
1 2 0
1
Sample Output 1
1
0
Explanation for Sample Output 1
Before the destruction, the path between planets 1 and 2 is boring. After destruction, the path between them doesn't exist anymore.
Sample Input 2
3
1 2 4
2 3 4
1 2
Sample Output 2
1
0
0
Explanation for Sample Output 2
Before the destruction, pair of planets
Sample Input 3
4
1 2 0
2 3 0
2 4 0
3 1 2
Sample Output 3
6
3
1
0
Explanation for Sample Output 3
Notice that in this example each pair of planets with a possible path between them is boring because all paths have the curiosity 0.
Comments