You are given an array a of length n = 2^m, where m ≥ 0. Write a function that finds length of the minimal period T of array a.

int MinPeriod(int * a, int n)

Number T is a period of array a, if repeating first T elements of array a several times gives exactly array a, without any extra elements.

Examples

INPUT: n = 8, a = {2, 5, 3, 4, 2, 5, 3, 4}
OUTPUT: 4

INPUT: n = 8 , a = {2, 5, 3, 2, 5, 3, 2, 5}
OUTPUT: 8

Solution should have a time complexity better than O(n²).