Code Solution

                                      E. Paint the Middle

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given n$n$ elements numbered from 1$1$ to n$n$, the element i$i$ has value ai$a_i$ and color ci$c_i$, initially, ci=0$c_i=0$ for all i$i$.

The following operation can be applied:

• Select three elements i$i$, j$j$ and k$k$ (1≤i<j<k≤n$1\le i<j<k\le n$), such that ci$c_i$, cj$c_j$ and ck$c_k$ are all equal to 0$0$ and ai=ak$a_i=a_k$, then set cj=1$c_j=1$.

Find the maximum value of ∑i=1nci$\sum _{i=1}^n{c}_i$ that can be obtained after applying the given operation any number of times.

Input

The first line contains an integer n$n$ (3≤n≤2⋅105$3\le n\le 2\cdot {10}^5$) — the number of elements.

The second line consists of n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$), where ai$a_i$ is the value of the i$i$-th element.

Output

Print a single integer in a line — the maximum value of ∑i=1nci$\sum _{i=1}^n{c}_i$ that can be obtained after applying the given operation any number of times.

Note

In the first test, it is possible to apply the following operations in order:

Solution:

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long
4. ll gcd(ll a,ll b)
5. {
7. if(a>b)
8. return gcd(b,a);
9. if(b%a==0)
10. return a;
11. return gcd(a,b%a);
12. }
13. void solve()
14. {
15. ll n;
16. cin>>n;
17. vector<ll>a(n);
18. vector<ll>b(n);
20. for(ll i=0;i<n;i++)
21. {
22. cin>>a[i];
23. }
24. for(ll i=0;i<n;i++)
25. {
26. cin>>b[i];
27. }
28. ll mxa=0,mxb=0;
29. for(ll i=0;i<n;i++)
30. {
31. ll mn=min(a[i],b[i]);
32. ll mx=max(a[i],b[i]);
33. mxa=max(mxa,mx);
34. mxb=max(mxb,mn);
35. }
36. cout<<mxa*mxb<<endl;
37. }
38. int main()
39. {
40. ll t; cin>>t;
41. while(t--)
42. {
43. solve();
44. }
45. }