DMOPC '22 Contest 5 P3 - Sorted XOR

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Anthony is obsessed with sorting algorithms. After mastering a couple different sorting algorithms, he is now learning how to solve more unconventional sorting problems. Initially, there is an array A of size N. Anthony can perform the following operation any number of times: change an element of A to any arbitrarily large non-negative integer. Let the array B be the prefix bitwise XOR array of A. Formally, B_{i} = A_{1} \oplus A_{2} \oplus ... \oplus A_{i}. Please tell Anthony the minimum number of operations to sort B in non-decreasing order.


1 \le N \le 10^6

0 \le A_i < 2^{30}

Subtask 1 [20%]

1 \le N \le 10^3

0 \le A_i < 2^{8}

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains the integer N.

The next line contains N space-separated integers, representing the array A.

Output Specification

Output the minimum number of operations to make B nondecreasing.

Sample Input

2 2 4

Sample Output


Explanation for Sample

1 operation can be performed by changing the first element to 0, making B nondecreasing.


There are no comments at the moment.