Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define sqrt sqrtl
- #define endl "\n"
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define pb push_back
- #define F first
- #define S second
- //3
- //4
- //4 4 4 4
- //0
- //4
- //1 2 4 4
- //1
- void solve() {
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- ll t = 1;
- cin >> t;
- //ll iff = 0;
- //1 1 2 1 4 4 1
- while (t--) {
- ll n;
- cin >> n;
- vector<vector<ll>>dp(n, vector<ll>(201,0));
- vector<ll>a(n);
- for (ll i = 0; i < n; i++)
- cin >> a[i];
- ll cur = 200;
- dp[0][a[0]]++;
- ll count = 0;
- for (ll i = 1; i < n; i++) {
- for (ll j = 1; j <= cur; j++) {
- dp[i][j] = dp[i - 1][j] + (a[i] == j);
- }
- }
- for (ll i = 1; i <= cur; i++) {
- if (dp[n - 1][i])
- count++;
- }
- if (count == n) {
- cout << 1 << endl;
- continue;
- }
- if (count == 1) {
- for (ll i = 1; 1 <= cur; i++) {
- if (dp[n - 1][i]) {
- //cout << "case #" << iff << ' ';
- cout << dp[n - 1][i] << endl;
- //iff++;
- break;
- }
- }
- continue;
- }
- else if (count == 2) {
- ll cnt = 0;
- ll loll = -1;
- for (ll i = 1; i < n; i++) {
- if (a[i] != a[i - 1]) {
- cnt++;
- loll = max(dp[n - 1][a[i]], dp[n - 1][a[i - 1]]);
- i ++;
- }
- }
- if (cnt == 1) {
- //cout << "case #" << iff<<' ';
- cout<< loll << endl;
- //iff++;
- continue;
- }
- }
- ll mx = -1;
- for (ll i = 0; i < n; i++) {
- for (ll j = 1; j <= cur; j++) {
- ll check = dp[n - 1][j] - 2 * dp[i][j];
- if (dp[n - 1][j] - 2 * dp[i][j] >= 0) {
- ll l = i, r = n;
- while (r - l > 1) {
- ll mid = (r + l) / 2;
- if (dp[mid][j] - 2*dp[i][j] >= 0) {
- r = mid;
- }
- else l = mid;
- }
- ll mex = -1;
- for (ll f = 1; f <= cur; f++) {
- if(f!=j)
- mex = max(dp[l][f] - dp[i][f], mex);
- }
- mx = max(mex + 2 * dp[i][j], mx);
- }
- }
- }
- //cout << "case #" << iff << ' ';
- cout << mx << endl;
- // iff++;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement