Is there any benefit of taking a subarray which contains more than 2 occurence of val?

Let us prove that the answer is an subarray which contains only two occurence of val, where the first and last element are val.
Firstly, any subarray which does not contain val as first/last element is not optimal as this subarray can be trimmed to such a state which improves the ratio.
Let $$$a$$$ be the smallest distance between any two occurrence of val in the array. The answer for this subarray is 2/(a+2).
It is easy to see that adding any occurence at a distance >$$$a$$$ can never give better answer.
Now it is needed to prove that adding more occurence at distance $$$a$$$ also does not improve the answer.
Let us add y occurence of val at a distance $$$a$$$.
The new ratio is (2 + y ) / (y*a + y + 2).
If this ratio is better, (2 + y ) / (y*a + y + 2 + a) > 2 / a+2
2*a + y*a + 2*y + 4 > 2*y*a + 2y + 4 + 2*a
0 > y*a
0 > y
By contradiction, it is shown that we must not add any more occurrences.

//Author Solution
#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
 ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
map<int,set<int>>m;
map<int,set<pair<int,int>>>track;
int a[n+1];
for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    a[i]=x;
    m[x].insert(i);
}
for(auto &it:m)
{
    int temp=-1;
    for(auto &trav:it.second)
    {
        if(temp==-1)
        temp=trav;
        else
        {
            track[it.first].insert({trav-temp,temp});
            temp=trav;
        }
    }
}
int q;
cin>>q;
while(q--)
{
    int check;
    cin>>check;
    if(check==1)
    {
        int x;
        cin>>x;
        if(track[x].empty())
        {
            cout<<-1<<'\n';
            continue;
        }
        auto it=*track[x].begin();
        cout<<it.second<<" "<<it.second+it.first<<endl;
    }
    else
    {
        int indx,y;
        cin>>indx>>y;
        int temp=a[indx];
        auto it=m[temp].find(indx);
        int left=-1,right=-1;
        if(it!=m[temp].begin())
        {
            auto it1=it;
            it1--;
            left=(*it1);
            track[temp].erase(track[temp].find({((*it)-(*it1)),(*it1)}));
        }
        auto it1=it;
        it1++;
        if(it1!=m[temp].end())
        {
            right=(*it1);
            track[temp].erase(track[temp].find({((*it1)-(*it)),(*it)}));
              
        }
        if(left!=-1&&right!=-1)
        {
            track[temp].insert({right-left,left});
        }
        m[temp].erase(it);
        m[y].insert(indx);
        
        it=m[y].find(indx);
        left=-1,right=-1;
        if(it!=m[y].begin())
        {
            auto it1=it;
            it1--;
            track[y].insert({((*it)-(*it1)),(*it1)});
            left=(*it1);
        }
        it1=it;
        it1++;
        if(it1!=m[y].end())
        {
              track[y].insert({((*it1)-(*it)),(*it)});
              right=(*it1);
        }
        a[indx]=y;
        if(left!=-1&&right!=-1)
        {
            track[y].erase(track[y].find({right-left,left}));
        }
    }
}
 return 0;
}

```cpp //Another solution

include<bits/stdc++.h>

using namespace std; vectora; unordered_map<int,set>m1; unordered_map<int,multiset<pair<int,pair<int,int>>>>m2; void query1(int value){ if(m2.count(value)==0){ cout<<-1<<endl;return; } cout<<m2[value].begin()->second.first<<' '<<m2[value].begin()->second.second<<endl; }

void query2(int x,int y){ auto it=m1[a[x]].find(x);auto it1=it,it2=it; if(it1!=m1[a[x]].begin()){ it1--; m2[a[x]].erase({*it-*it1,{*it1,*it}}); } if(it2!=(--m1[a[x]].end())){ it2++; m2[a[x]].erase({*it2-*it,{*it,*it2}}); } if(it2!=it&&it1!=it) { m2[a[x]].insert({*it2-*it1,{*it1,*it2}}); } m1[a[x]].erase(it); if(m1[a[x]].size()==0)m1.erase(a[x]); if(m2[a[x]].size()==0)m2.erase(a[x]); a[x]=y; m1[y].insert(x); it=m1[y].find(x);it1=it,it2=it; if(it1!=m1[y].begin()){ it1--; m2[a[x]].insert({*it-*it1,{*it1,*it}}); } if(it2!=(--m1[y].end())){ it2++; m2[a[x]].insert({*it2-*it,{*it,*it2}}); } if(it2!=it&&it1!=it) { m2[a[x]].erase({*it2-*it1,{*it1,*it2}}); }

}

int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; a.resize(n); for(int &it:a)cin>>it; for(int i=0;i<n;i++){ m1[a[i]].insert(i); } for(auto &it:m1){ multiset<pair<int,pair<int,int>>>&itr=m2[it.first]; vectortemp(it.second.begin(),it.second.end()); for(int i=0;i+1<temp.size();i++){ itr.insert({temp[i+1]-temp[i],{temp[i],temp[i+1]}}); } } int q;cin>>q; for(int i=0;i<q;i++){ int type;cin>>type; if(type==1){ int x;cin>>x; query1(x); }else{ int x,y;cin>>x>>y; query2(x,y); } } }

D — Subarray mysteries

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll __int128
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long double,int>, null_type,
      less<pair<long double,int>>, rb_tree_tag,
      tree_order_statistics_node_update>
      Pbds;


const char nl = '\n';
bitset<1000010> iscomp;
int highest[1000010];
void sieve()
{
    for (int i = 2; i < 1000010; i++)
    {
        if (!iscomp[i])
        {
            highest[i]=i;
            for (int j = i * i; j < 1000010; j += i)
            {
                highest[j]=i;
                iscomp[j] = 1;
            }
        }
    }
}
int n,k;
void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void solve(int testcase)
{
    cin>>n>>k;
    vector<int>a(n);
    for(int &it:a)cin>>it;
    map<int,vector<int>>m;
    for(int i=0;i<n;i++){
        m[a[i]].push_back(i);
    }
    long double K=k;
    for(auto &it:m){
        cout<<it.first<<' ';
        if(it.second.size()==1){
            cout<<0<<endl;continue;
        }
        Pbds s;
        s.insert({K-1000-K*it.second[0],0});
        int ans=0;
        for(int i=1;i<it.second.size();i++){
            int p=s.order_of_key({i*1000-K*it.second[i],INT_MAX});
            ans+=p;
            s.insert({K-1000-K*it.second[i]+i*1000,i});
        }
        cout<<ans<<' ';
        cout<<endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //sieve();
    int t = 1;
    //cin >> t;
    for (int p = 1; p <= t; p++)
    {
        solve(p);
    }
}

#include<bits/stdc++.h>
using namespace std;

#define int long long

// LCA code source - usaco.guide
int depth[200010];
int up[200010][20];
int score[200010];
vector<int> adj[200010];

void dfs(int v) {
    for(int i = 1; i < 20; i++) { up[v][i] = up[up[v][i - 1]][i - 1]; }
    for (int x : adj[v]) {
        if (x != up[v][0]) {
            depth[x] = depth[up[x][0] = v] + 1;
            dfs(x);
        }
    }
}

int jump(int x, int d) {
    for(int i = 0; i < 20; i++) {
        if ((d >> i) & 1) x = up[x][i];
    }
    return x;
}

int LCA(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    a = jump(a, depth[a] - depth[b]);
    if (a == b) return a;

    for(int i = 19; i >= 0; i--) {
        int aT = up[a][i], bT = up[b][i];
        if (aT != bT) a = aT, b = bT;
    }

    return up[a][0];
}

void clear(int n) {
    for(int i = 0; i < n; i++) {
        score[i] = 0;
        depth[i] = 0;
        adj[i].clear();
        for(int j = 0; j < 20; j++) 
            up[i][j] = 0;
    }   
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        clear(n + 5);

        for(int i = 0; i < n - 1; i++) {
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        dfs(1);

        for(int i = 1; i < n; i++) {
            int par = LCA(i, i + 1);
            score[up[i][0]]++, score[i + 1]++;
            score[par]--, score[up[par][0]]--;
        }
        
        vector<pair<int,int>> vp;
        for(int i = 2; i <= n; i++) {
            vp.push_back({-depth[i], i});
        }
        sort(vp.begin(), vp.end());

        for(int i = 0; i < vp.size(); i++) {
            score[up[vp[i].second][0]] += score[vp[i].second];
        }

        score[1]++; // initial stand
        for(int i = 1; i <= n; i++) cout << score[i] << " ";
        cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 998244353

const int N=1e5;

int binexp(int a, int b) {
    int res = 1;
    while (b > 0) {
        if(b&1)
        res = ((res%MOD)*(a%MOD))%MOD;
        a = ((a%MOD)*(a%MOD))%MOD;
        b >>= 1;
    }
    return res;
}

void solve(){
    int n;
    string a,b;
    cin >> n >> a >> b;
    int an = stoi(a.substr(7,3));
    int bn = stoi(b.substr(7,3));
    int ans = 0;
    for(int i=1;i<=n;i++){
        if((an-1)/i == (bn-1)/i){
            ans++;
        }
    }
    
    ans *= binexp(n,MOD-2);
    ans %= MOD;

    cout << ans << endl;

}

int32_t main()
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

#ifndef ONLINE_JUDGE
    freopen("test0.in", "r", stdin);
    freopen("test0.out", "w", stdout);
#endif

    int t = 1;
    cin >> t;
    while (t--)
        solve();
        
    return 0;
}