Minimum no of swaps to be done in an array such that, no two adjacent elements are same

Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex-

n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a with a or a )

n = 8, a[] = {1, 5, 5, 1, 4, 6, 1, 1}, answer = 2, (swap (a with a) and (a with a) )

n = 8, a[] = {3, 1, 1, 5, 3, 3, 5, 5}, answer = 2, (swap (a with a) and (a with a) )

(0-based indexing used in above examples.)

I came up with a recursive/backtracking solution for it.

int finalans=INT_MAX;
bool check(vector<int> a)
{
for(int i=1;i<a.size();i++)
{
if(a[i-1]==a[i])
return false;
}
return true;
}
void minimumSwaps(vector<int> &a, int swaps=0,int idx)
{
if(check(a))
{
finalans=min(finalans,swaps);
}
for(int i=idx;i<a.size();i++)
{
for(int j=i+1;j<a.size();j++)
{
swap(a[i],a[j]);
minimumSwaps(a,swaps+1,i+1);
swap(a[i],a[j]);
}
}
}

int main(){
int n;cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];

minimumSwaps(a,0,0);

cout<<finalans<<endl;
}

However if the length of array is of order 10^5, Time complexity will become very large. Is there any way to do it in polynomial time complexity?

Update: I found this question on the discussion forum of codeforces (link) and similar question using strings on leetcode (link) as well.