Fun with Even Subarrays Solution|Codeforces round #768 (div 2)

                         Fun with Even Subarrays

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a$a$ of n$n$ elements. You can apply the following operation to it any number of times:

• Select some subarray from a$a$ of even size 2k$2k$ that begins at position l$l$ (1≤l≤l+2⋅k−1≤n$1\le l\le l+2\cdot k-1\le n$, k≥1$k\ge 1$) and for each i$i$ between 0$0$ and k−1$k-1$ (inclusive), assign the value al+k+i$a_{l+k+i}$ to al+i$a_{l+i}$.

For example, if a=[2,1,3,4,5,3]$a=[2,1,3,4,5,3]$, then choose l=1$l=1$ and k=2$k=2$, applying this operation the array will become a=[3,4,3,4,5,3]$a=[3,4,3,4,5,3]$.

Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal.

Input

The input consists of multiple test cases. The first line contains a single integer t$t$ (1≤t≤2⋅104$1\le t\le 2\cdot {10}^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$) — the length of the array.

The second line of each test case consists of n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$) — the elements of the array a$a$.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

Print t$t$ lines, each line containing the answer to the corresponding test case — the minimum number of operations needed to make equal all the elements of the array with the given operation.

Note

In the first test, all elements are equal, therefore no operations are needed.

In the second test, you can apply one operation with k=1$k=1$ and l=1$l=1$, set a1:=a2$a_1:=a_2$, and the array becomes [1,1]$[1,1]$ with 1$1$ operation.

In the third test, you can apply one operation with k=1$k=1$ and l=4$l=4$, set a4:=a5$a_4:=a_5$, and the array becomes [4,4,4,4,4]$[4,4,4,4,4]$.

In the fourth test, you can apply one operation with k=1$k=1$ and l=3$l=3$, set a3:=a4$a_3:=a_4$, and the array becomes [4,2,3,3]$[4,2,3,3]$, then you can apply another operation with k=2$k=2$ and l=1$l=1$, set a1:=a3$a_1:=a_3$, a2:=a4$a_2:=a_4$, and the array becomes [3,3,3,3]$[3,3,3,3]$.

In the fifth test, there is only one element, therefore no operations are needed.

Solution:

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define pb emplace_back
4. #define pob pop_back
5. typedef long long int lli;
6. #define test lli t; cin>>t; while(t--)
7. #define ff first
8. #define ss second
9. #define F(n) for(lli i=0;i<n;i++)
10. #define pf pop_front
11. #define lb lower_bound
12. #define ub upper_bound
13. #define setbits(x) __builtin_popcountll(x)
14. #define zerobits(x) __builtin_ctzll(x)
15. #define bs binary_search
16. #define all(x) x.begin(),x.end()
17. #define nl "\n"
18. #define loop(i,s,n) for(lli i=s;i<n;i++)
19. #define pp(a) for(auto x : a) cout<<x<<" "; cout<<nl;
20. #define mem(arr,x) memset(arr,x,sizeof(arr))
21. #define mod 1000000007
22. #define inf 1e18
23. #define N 100005
24. #define tt(n) cin>>n; lli a[n]; loop(i,0,n) cin>>a[i];
25. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
26. #define ps(x,y) fixed<<setprecision(y)<<x
27.  
28. int main()
29. {
30. fast;
31. // #ifndef ONLINE_JUDGE
32. // freopen("input.txt", "r", stdin);
33. // freopen("output.txt", "w", stdout);
34. // #endif
35. lli n,i,j,k;
36. test
37. {
38. cin>>n>>k;
39. lli sum=0;
40. loop(i,0,n)
41. {
42. if(i%2==0)
43. {
44. sum+=(i&(i+1));
45. }
46. }
47. // cout<<sum<<" ";
48. if(k>sum) cout<<-1<<nl;
49. else
50. {
51. if(k==n-1)
52. {
53. cout<<n-2<<" "<<n-1<<nl;
54. cout<<"1 3"<<nl;
55. i=0;j=n-3;
56. while(i<j)
57. {
58. if(i==1 || i==3) { i++; continue; }
59. if(j==1 || j==3) { j--; continue; }
60. cout<<i<<" "<<j<<nl;
61. i++;j--;
62. }
63. }
64. else
65. {
66. cout<<k<<" "<<n-1<<nl;
67. if(k!=0)
68. cout<<0<<" "<<n-1-k<<nl;
69. i=1;j=n-2;
70. while(i<j)
71. {
72. if(i==k || j==k)
73. {
74. i++;
75. j--;
76. }
77. else
78. {
79. cout<<i<<" "<<j<<nl;
80. i++;j--;
81. }
82. }
83. }
84. }
85. // cout<<nl;
86. }
87. return 0;
88. }