#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N],f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==a[i-1]&&i!=1)
        {
            n--;
            i--;
        }
    }
    for(int len=2;len<=n;len++)
    {
        for(int j=1;j+len-1<=n;j++)
        {
            int r=j+len-1;
            if(a[j]!=a[r]) f[j][r]=min(f[j+1][r]+1,f[j][r-1]+1);
            else  f[j][r]=f[j+1][r-1]+1;
        }
    }
    cout<<f[1][n];
    return 0; 
}

#include<bits/stdc++.h>
using namespace std;
int a[50010];
int f[50010],g[50010],b[50010];
int inf=1e9;
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    f[0]=g[0]=-inf;
    for(int i=1;i<=n;i++)
    {
        f[i]=max(a[i],a[i]+f[i-1]);
        g[i]=max(f[i],g[i-1]);
    }
    b[n+1]=f[n+1]=-inf;
    for(int i=n;i;i--)
    {
        f[i]=max(f[i+1]+a[i],a[i]);
        b[i]=max(b[i+1],f[i]);
    }
    int sum=-inf;
    for(int i=1;i<=n;i++)
    {
        sum=max(sum,g[i]+b[i+1]);
    }
    cout<<sum<<endl;
}
int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
    cin>>n;
    cin>>s;
    for(int i=1;i<=n;i++)
    {
        bool flag=true;
        unordered_set<string> st;
        for(int j=0;j+i<=n;j++)
        {
            string ss=s.substr(j,i);
            if(st.count(ss)!=0)
            {
                flag=false;
                break;
            }
            st.insert(ss);
        }
        if(flag) {cout<<i<<endl; break;}
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2*10e5+10;
int a[N];
int n;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {

        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int l=n+5;
        for(int i=n;i>=1;i--)
        {
            l=min(l,i-a[i]+1);
            if(l<=i) a[i]=1;
        }

        for(int j=1;j<=n;j++) cout<<a[j]<<' ';
        cout<<endl;
    }

    return 0; 
}

#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {int x; cin>>x; a[i]=a[i-1]+x;}
    while(m--)
    {
        int p,q;
        cin>>p>>q;
        cout<<a[q]-a[p-1]<<endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N];
int main()
{
    LL cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++) {int x;cin>>x; a[i]+=a[i-1]+x;}
    if(n<3||a[n]%3) cout<<0<<endl;
    else
    {
        LL res=0;
        for(int j=2;j<n;j++)
        {
            if(a[j-1]==a[n]/3) res++;
            if(a[j]==a[n]/3*2) cnt+=res;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010, mod = 100003;

int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];
int q[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    cnt[1]=1;
    int hh=0,tt=0;
    q[0]=1;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+1)
            {
                dist[j]=dist[t]+1;
                cnt[j]=cnt[t];
                q[++tt]=j;
            }
            else if(dist[j]==dist[t]+1)
            {
                cnt[j]=(cnt[j]+cnt[t])%mod;
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bfs();
    for(int i=1;i<=n;i++) cout<<cnt[i]<<endl;
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 11, M = 360, P = 1 << 10;

int n,m,k,p;
int h[N*N],e[M],w[M],ne[M],idx;
int g[N][N],key[N*N];
int dist[N*N][P];
bool st[N*N][P];

set<PII> edges;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void build()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int u = 0; u < 4; u ++ )
            {
                int x = i + dx[u], y = j + dy[u];
                if (!x || x > n || !y || y > m) continue;
                int a = g[i][j], b = g[x][y];
                if (!edges.count({a, b})) add(a, b, 0);
            }
}

int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    deque<PII> q;
    q.push_back({1,0});
    while(q.size())
    {
        PII t=q.front();
        q.pop_front();
        if(st[t.x][t.y]) continue;
        st[t.x][t.y]=true;
        if (t.x == n * m) return dist[t.x][t.y];
        if(key[t.x])
        {
            int state=t.y|key[t.x];
            if(dist[t.x][state]>dist[t.x][t.y])
            {
                dist[t.x][state]=dist[t.x][t.y];
                q.push_front({t.x, state});
            }
        }
        for (int i = h[t.x]; ~i; i = ne[i])
        {
            int j=e[i];
            if (w[i]!=0 && !(t.y >> w[i] - 1 & 1)) continue; 
            if(dist[j][t.y] > dist[t.x][t.y] + 1)
            {
                dist[j][t.y]=dist[t.x][t.y] + 1;
                q.push_back({j, t.y});
            }
        }
    }
    return -1;
}

int main()
{
    cin>>n>>m>>p>>k;
    for(int i=1,t=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        g[i][j]=t++;
    memset(h,-1,sizeof h);
    while(k--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        int a = g[x1][y1], b = g[x2][y2];
        edges.insert({a, b}), edges.insert({b, a});
        if (c) add(a, b, c), add(b, a, c);
    }
    build();
    int s;
    cin>>s;
    while(s--)
    {
        int x,y,c;
        cin>>x>>y>>c;
        key[g[x][y]]|=1<<c-1;

    }
    cout << bfs() << endl;

    return 0;

}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 21010, INF = 0x3f3f3f3f; //建虚拟边需要多开1000条边


int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;   
}


void spfa()
{
    int hh=0,tt=1; 
    q[0]=0;
        memset(dist, 0x3f, sizeof dist);
    dist[0]=0;
   /* int scnt;
    cin>>scnt;
         int hh=0,tt=1; 
    memset(dist, 0x3f, sizeof dist);
    while(scnt--)
    {
        int u;
        cin>>u;
        dist[u]=0;
        q[tt++]=u;
        st[u]=true;
    }*/
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if (!st[j])
                {
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }

}

int main()
{
    while(scanf("%d%d%d", &n, &m, &T) != -1)
    {
        memset(h, -1, sizeof h);
        idx=0;
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        int s;
        cin>>s;
        while(s--)
        {
            int ver;
            scanf("%d",&ver);//输入多个原点
            add(0,ver,0);//建立价值为0的边
        }
        spfa();
        if(dist[T]==INF) cout<<-1<<endl;
        else cout<<dist[T]<<endl;
    }

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 2000010;
int n, m;
int w[N];
int hs[N], ht[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
int q[N];
bool st[N];

void add(int h[],int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int h[],int dist[],int type)
{
     int hh = 0, tt = 1;
      if (type == 0)
    {
        memset(dist, 0x3f, sizeof dmin);
        dist[1] = w[1];
        q[0] = 1;
    }
    else
    {
        memset(dist, -0x3f, sizeof dmax);
        dist[n] = w[n];
        q[0] = n;
    }
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(type==0&&dist[j]>min(dist[t],w[j])||type==1&&dist[j]<max(dist[t],w[j]))
            {
                if (type == 0) dist[j] = min(dist[t], w[j]);
                else dist[j] = max(dist[t], w[j]);
                 if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }

    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    memset(hs,-1,sizeof hs);
    memset(ht,-1,sizeof ht);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(hs,a,b),add(ht,b,a);
        if(c==2) add(hs,b,a) ,add(ht,a,b);
    }
    spfa(hs,dmin,0);
    spfa(ht,dmax,1);
    int res=0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);
    cout<<res;
    return 0; 
}