Codeforces Round ＃799 (Div. 4)A~H

Codeforces Round #799 (Div. 4)

Problem - A - Codeforces

You are given four distinct integers a, b, c, d.

Timur and three other people are running a marathon. The value a is the distance that Timur has run and b, c, d correspond to the distances the other three participants ran.

Output the number of participants in front of Timur.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The description of each test case consists of four distinct integers a, b, c, d (0≤a,b,c,d≤104).

Output

For each test case, output a single integer — the number of participants in front of Timur.

Example

input

4
2 3 4 1
10000 0 1 2
500 600 400 300
0 9999 10000 9998

output

2
0
1
3

Problem analysis

Here you are. 4 Individual displacement length , How many people are in front of the first one .

The direct output displacement length is greater than the number of the first person .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int a;
        cin >> a;
        int res = 0;
        vector<int>v(3);
        for (int i = 0; i < 3; i++)
        {
            cin >> v[i];
            if (v[i] > a)res++;
        }
        cout << res << endl;
    }
    return 0;
}

Problem - B - Codeforces

Sho has an array a consisting of n integers. An operation consists of choosing two distinct indices i and j and removing ai and aj from the array.

For example, for the array [2,3,4,2,5], Sho can choose to remove indices 1 and 3. After this operation, the array becomes [3,2,5]. Note that after any operation, the length of the array is reduced by two.

After he made some operations, Sho has an array that has only distinct elements. In addition, he made operations such that the resulting array is the longest possible.

More formally, the array after Sho has made his operations respects these criteria:

No pairs such that (i<j) and ai=aj exist.
The length of a is maximized.
Output the length of the final array.

Input

The first line contains a single integer t (1≤t≤103) — the number of test cases.

The first line of each test case contains a single integer n (1≤n≤50) — the length of the array.

The second line of each test case contains n integers ai (1≤ai≤104) — the elements of the array.

Output

For each test case, output a single integer — the length of the final array. Remember that in the final array, all elements are different, and its length is maximum.

Example

input

4
6
2 2 2 3 3 3
5
9 1 9 9 1
4
15 16 16 15
4
10 100 1000 10000

output

2
1
2
4

Problem analysis

Give you an array , You can delete two numbers at a time , Ask you to change the array to have no repeating elements , What is the maximum length of the array .

Record the number of occurrences of each number , Look at the number of odd numbers , How many numbers are even . If the number of occurrences is odd , Then you can leave a number after deleting the same , If the number of occurrences is even , Then we have to judge again , How many of them appear in an even number ：

If it's an even number （ for example ：1,1,2,2）, Then it can be digested internally （ Delete one 1 And a 2), The last remaining number is : Odd numbers + Even numbers ;

If it's an odd number （ for example ：1,1,2,2,3,3）, Then the last remaining number is ： Odd numbers + Even numbers -1;

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int>v(n);
        unordered_map<int, int>mymap;
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
            mymap[v[i]]++;
        }
        int ji = 0, ou = 0;
        for (auto i : mymap)
        {
            if (i.second % 2 == 0)ou++;
            else ji++;
        }
        if (ou % 2 == 0)
        {
            cout << ji + ou << endl;
        }
        else cout << ji + ou - 1 << endl;
    }
    return 0;
}

Problem - C - Codeforces

Mihai has an 8×8 chessboard whose rows are numbered from 1 to 8 from top to bottom and whose columns are numbered from 1 to 8 from left to right.

Mihai has placed exactly one bishop on the chessboard. The bishop is not placed on the edges of the board. (In other words, the row and column of the bishop are between 2 and 7, inclusive.)

The bishop attacks in all directions diagonally, and there is no limit to the distance which the bishop can attack. Note that the cell on which the bishop is placed is also considered attacked.

An example of a bishop on a chessboard. The squares it attacks are marked in red.

Mihai has marked all squares the bishop attacks, but forgot where the bishop was! Help Mihai find the position of the bishop.

Input

The first line of the input contains a single integer t (1≤t≤36) — the number of test cases. The description of test cases follows. There is an empty line before each test case.

Each test case consists of 8 lines, each containing 8 characters. Each of these characters is either ‘#’ or ‘.’, denoting a square under attack and a square not under attack, respectively.

Output

For each test case, output two integers r and c (2≤r,c≤7) — the row and column of the bishop.

The input is generated in such a way that there is always exactly one possible location of the bishop that is not on the edge of the board.

Example

input

3

.....#..
#...#...
.#.#....
..#.....
.#.#....
#...#...
.....#..
......#.

#.#.....
.#......
#.#.....
...#....
....#...
.....#..
......#.
.......#

.#.....#
..#...#.
...#.#..
....#...
...#.#..
..#...#.
.#.....#
#.......

output

4 3
2 2
4 5

Problem analysis

The title is for you 8*8 The chessboard of , A chess piece can attack its diagonal direction （ The attack range is ‘#’）, Let you find the position of this chess piece . And this piece will not appear on the edge .

ergodic matrix , Find a place （x,y）, The character in this position is ’#', And its diagonal four directions （x-1,y-1）,（x-1,y+1）,（x+1,y+1）,（x+1,y-1） All of them are ‘#’, Find and output .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        vector<string>v(8);
        for (int i = 0; i < 8; i++)
        {
            cin >> v[i];
        }
        bool flag = false;
        int x, y;
        for (int i = 1; i < 8; i++)
        {
            for (int j = 1; j < 8; j++)
            {
                if (v[i][j] == '#' && v[i + 1][j + 1] == '#' && v[i - 1][j - 1] == '#' && v[i + 1][j - 1] == '#' && v[i - 1][j + 1] == '#')
                {
                    x = i, y = j, flag = true;
                    break;
                }
            }
            if (flag)break;
        }
        cout << x+1 << " " << y+1 << endl;
    }
    return 0;
}

Problem - D - Codeforces

Victor has a 24-hour clock that shows the time in the format “HH:MM” (00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59). He looks at the clock every x minutes, and the clock is currently showing time s.

How many different palindromes will Victor see in total after looking at the clock every x minutes, the first time being at time s?

For example, if the clock starts out as 03:12 and Victor looks at the clock every 360 minutes (i.e. every 6 hours), then he will see the times 03:12, 09:12, 15:12, 21:12, 03:12, and the times will continue to repeat. Here the time 21:12 is the only palindrome he will ever see, so the answer is 1.

A palindrome is a string that reads the same backward as forward. For example, the times 12:21, 05:50, 11:11 are palindromes but 13:13, 22:10, 02:22 are not.

Input

The first line of the input contains an integer t (1≤t≤100) — the number of test cases. The description of each test case follows.

The only line of each test case contains a string s of length 5 with the format “HH:MM” where “HH” is from “00” to “23” and “MM” is from “00” to “59” (both “HH” and “MM” have exactly two digits) and an integer x (1≤x≤1440) — the number of minutes Victor takes to look again at the clock.

Output

For each test case, output a single integer — the number of different palindromes Victor will see if he looks at the clock every x minutes starting from time s.

Example

input

6
03:12 360
00:00 1
13:22 2
15:15 10
11:11 1440
22:30 27

output

1
16
10
0
1
1

Problem analysis

The title is to give you a current time s, Then I'll give you another minute m, Let you every m Look at the clock in minutes , If the current clock number can form a palindrome string （21:12） Just record it , How many palindromes can you see in a reincarnation .

Just put the given time s Convert to hours x And minutes y Two variables , Reuse a and b Indicates the hours and minutes seen when looking at the clock , For convenience, you can also count the minutes m It also translates into hours and minutes . When ax And by It means to complete a reincarnation . Then judge whether it is palindrome a and b Is it the opposite number （ such as 21 and 12） that will do .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

bool check(int a,int b)
{
    string s1 = to_string(a), s2 = to_string(b);
    if (s1.size() < 2)s1 = "0" + s1;
    if (s2.size() < 2)s2 = "0" + s2;
    reverse(s1.begin(), s1.end());
    return s1 == s2;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        int ans;
        cin >> s >> ans;
        int res = 0;
        int h = ans / 60, m = ans % 60;
        int x = stoi(s.substr(0, 2)), y = stoi(s.substr(3, 2));
        if (check(x, y))res++;
        int b = y + m, a = h + x + (b) / 60;
        b %= 60;
        a %= 24;
        while (a != x || b != y)
        {
            if (check(a, b))res++;
            b += m;
            a += h + b / 60;
            a %= 24;
            b %= 60;
        }
        cout << res << endl;
    }
    return 0;
}

Problem - E - Codeforces

Slavic has an array of length n consisting only of zeroes and ones. In one operation, he removes either the first or the last element of the array.

What is the minimum number of operations Slavic has to perform such that the total sum of the array is equal to s after performing all the operations? In case the sum s can’t be obtained after any amount of operations, you should output -1.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains two integers n and s (1≤n,s≤2⋅105) — the length of the array and the needed sum of elements.

The second line of each test case contains n integers ai (0≤ai≤1) — the elements of the array.

It is guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.

Output

For each test case, output a single integer — the minimum amount of operations required to have the total sum of the array equal to s, or -1 if obtaining an array with sum s isn’t possible.

Example

input

7
3 1
1 0 0
3 1
1 1 0
9 3
0 1 0 1 1 1 0 0 1
6 4
1 1 1 1 1 1
5 1
0 0 1 1 0
16 2
1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1
6 3
1 0 1 0 0 0

output

0
1
3
2
2
7
-1

Problem analysis

The title is to give you an all by 0 and 1 Composed of an array and a number k, You can delete the head or tail elements of the array every time , Ask how many elements you should delete at least , Make the sum of the array k.

Dichotomy , Make two auxiliary arrays lx and rx, Stored are pairs ,lx[i].first It means the number from left to right 1,lx[i].second Represents to this 1 How many elements need to be deleted ;rx Empathy , But from right to left . We fixed traversal left endpoint , Every time you traverse a segment , Just use two points to find the point we need on the right , In calculating the number of steps to the left endpoint + The number of steps to the right endpoint , Maintain the minimum value during this process .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k, sum = 0;
        cin >> n >> k;
        vector<int>v(n + 1);
        vector<PII>lx,rx;
        lx.push_back({ 0,0 });
        rx.push_back({ 0,0 });
        for (int i = 1; i <= n; i++)
        {
            cin >> v[i];
            if (v[i] == 1)
            {
                lx.push_back({ lx.back().first + 1,i });
            }
            sum += v[i];
        }
        for (int i = n; i >= 1; i--)
        {
            if (v[i] == 1)
            {
                rx.push_back({ rx.back().first + 1,n - i + 1 });
            }
        }
        if (sum == k)
        {
            cout << 0 << endl;
            continue;
        }
        else if (sum < k)
        {
            cout << -1 << endl;
            continue;
        }
        int res = 1e9;
        for (auto i : lx)
        {
            if (sum - i.first == k)
            {
                res = min(res, i.second);
                continue;
            }
            if (sum - i.first < k)
            {
                break;
            }
            int l = 0, r = rx.size() - 1;
            while (l < r)
            {
                int mid = (l + r) / 2;
                if (rx[mid].first == sum - k - i.first)
                {
                    l = mid;
                    break;
                }
                else if (rx[mid].first <= sum - k - i.first)l = mid;
                else r = mid;
            }
            res = min(res, i.second + rx[l].second);
        }
        cout << res << endl;
    }
    return 0;
}

Problem - F - Codeforces

Given an array a of positive integers with length n, determine if there exist three distinct indices i, j, k such that ai+aj+ak ends in the digit 3.

Input

The first line contains an integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains an integer n (3≤n≤2⋅105) — the length of the array.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array.

The sum of n across all test cases does not exceed 2⋅105.

Output

Output t lines, each of which contains the answer to the corresponding test case. Output “YES” if there exist three distinct indices i, j, k satisfying the constraints in the statement, and “NO” otherwise.

You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes” and “YES” will be recognized as a positive answer).

Example

input

6
4
20 22 19 84
4
1 11 1 2022
4
1100 1100 1100 1111
5
12 34 56 78 90
4
1 9 8 4
6
16 38 94 25 18 99

output

YES
YES
NO
NO
YES
YES

Problem analysis

The title is to give you an array , Ask if you can find in this array 3 Elements , Let their harmony %10 After equal to 3.

I wrote it by typing ：

contain 0 And the end is 3 The sum of three numbers of has ：0+1+2,0+0+3,0+4+9,0+5+8,0+6+7;

contain 1 Of ：0+1+2,1+1+1,1+3+9,1+4+8,1+5+7,1+6+6;

contain 2 Of ：0+1+2,1+1+1,1+3+9,1+4+8,1+5+7,1+6+6;

contain 3 Of ：0+0+3,1+3+9,2+3+8,3+3+7,3+4+6,3+5+5;

………………

First put all the elements %10, Then record the number of occurrences , Then judge whether it can meet the above situation , One thing that can be satisfied is yes.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int>v(n);
        unordered_map<int, int>mymap;
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
            v[i] %= 10;
            mymap[v[i]]++;
        }
        bool flag = false;
        if (!flag&&mymap[0] > 0)
        {
            if (mymap[1] > 0 && mymap[2] > 0)flag = true;
            if (mymap[3] > 0 && mymap[0] >= 2)flag = true;
            if (mymap[4] > 0 && mymap[9] > 0)flag = true;
            if (mymap[5] > 0 && mymap[8] > 0)flag = true;
            if (mymap[6] > 0 && mymap[7] > 0)flag = true;           
        }
        if (!flag && mymap[1] > 0)
        {
            if (mymap[2] > 0 && mymap[0] > 0)flag = true;
            if (mymap[1] >= 3)flag = true;
            if (mymap[3] > 0 && mymap[9] > 0)flag = true;
            if (mymap[4] > 0 && mymap[8] > 0)flag = true;
            if (mymap[5] > 0 && mymap[7] > 0)flag = true;
            if (mymap[6] >=2)flag = true;
        }
        if (!flag && mymap[2] > 0)
        {
            if (mymap[2] >= 2 && mymap[9] > 0)flag = true;
            if (mymap[3] > 0 && mymap[8] > 0)flag = true;
            if (mymap[4] > 0 && mymap[7] > 0)flag = true;
            if (mymap[5] > 0 && mymap[6] > 0)flag = true;
        }
        if (!flag && mymap[3] > 0)
        {
            if (mymap[3] >= 2 && mymap[7] > 0)flag = true;
            if (mymap[4] > 0 && mymap[6] > 0)flag = true;
            if (mymap[5] >= 2)flag = true;
        }
        if (!flag && mymap[4] > 0)
        {
            if (mymap[4] >= 2 && mymap[5] > 0)flag = true;
        }
        if (!flag && mymap[5] > 0)
        {
            if (mymap[9] >= 2 && mymap[5] > 0)flag = true;
        }
        if (!flag && mymap[6] > 0)
        {
            if (mymap[8] > 0 && mymap[9] > 0)flag = true;
        }
        if (!flag && mymap[7] > 0)
        {
            if (mymap[7] >= 2 && mymap[9] > 0)flag = true;
            if (mymap[8] >= 2)flag = true;
        }

        if (flag)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

Problem - G - Codeforces

Given an array a of length n and an integer k, find the number of indices 1≤i≤n−k such that the subarray [ai,…,ai+k] with length k+1 (not with length k) has the following property:

If you multiply the first element by 20, the second element by 21, …, and the (k+1)-st element by 2k, then this subarray is sorted in strictly increasing order.
More formally, count the number of indices 1≤i≤n−k such that
20⋅ai<21⋅ai+1<22⋅ai+2<⋯<2k⋅ai+k.

Input

The first line contains an integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains two integers n, k (3≤n≤2⋅105, 1≤k<n) — the length of the array and the number of inequalities.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array.

The sum of n across all test cases does not exceed 2⋅105.

Output

For each test case, output a single integer — the number of indices satisfying the condition in the statement.

Example

input

6
4 2
20 22 19 84
5 1
9 5 3 2 1
5 2
9 5 3 2 1
7 2
22 12 16 4 3 22 12
7 3
22 12 16 4 3 22 12
9 3
3 9 12 3 9 12 3 9 12

output

2
3
2
3
1
0

Problem analysis

The title is to give you an array and a value k, Let you find all the lengths k+1 And can meet (a[i]* 2^0 )<(a[i+1]*2^1 )<……(a[i+k] *2^k ) Subarray .

So let's analyze that , This subarray is multiplied by each element in order 2 Of i Power , And the array should be multiplied by the increasing form , Because by 2 Of i After power ,i+1 The number ratio of i Multiply the number of by one 2, in other words i+1 The number of must be at least greater than i Half of , Otherwise, the strict and increasing requirements cannot be met .

So let's go through the array , As long as the current element is half of the previous number, it is still large , Let's record this number as 1, On the contrary 0, Then we just need to find the interval length k+1, And the sum of intervals is k+1 That's enough . Be careful , The first number of each interval must be 0, When judging the sum of intervals , If the first number of the interval was originally recorded as 0, It should also be temporarily changed to 1. As for the fast calculation of interval sum , You can use segment tree or prefix and , For convenience, the prefix and .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n,k;
        cin >> n >> k;
        vector<int>v(n+1),ans(n+1),sum(n+1);
        for (int i = 1; i <= n; i++)
        {
            cin >> v[i];
            if (v[i] > v[i - 1] / 2)
            {
                ans[i] = 1;
            }
            sum[i] = sum[i - 1] + ans[i];
        }
        int res = 0;
        for (int i = k+1; i <= n; i++)
        {
            int r = sum[i], l = sum[i - k - 1];
            if (i-k!=1&&ans[i - k] == 0)r++;
            if (r - l >= k + 1)res++;
        }
        cout << res << endl;
    }
    return 0;
}

Problem - H - Codeforces

Marian is at a casino. The game at the casino works like this.

Before each round, the player selects a number between 1 and 109. After that, a dice with 109 faces is rolled so that a random number between 1 and 109 appears. If the player guesses the number correctly their total money is doubled, else their total money is halved.

Marian predicted the future and knows all the numbers x1,x2,…,xn that the dice will show in the next n rounds.

He will pick three integers a, l and r (l≤r). He will play r−l+1 rounds (rounds between l and r inclusive). In each of these rounds, he will guess the same number a. At the start (before the round l) he has 1 dollar.

Marian asks you to determine the integers a, l and r (1≤a≤109, 1≤l≤r≤n) such that he makes the most money at the end.

Note that during halving and multiplying there is no rounding and there are no precision errors. So, for example during a game, Marian could have money equal to 1/1024, 1/128, 1/2, 1, 2, 4, etc. (any value of 2t, where t is an integer of any sign).

Input

The first line contains a single integer t (1≤t≤100) — the number of test cases.

The first line of each test case contains a single integer n (1≤n≤2⋅105) — the number of rounds.

The second line of each test case contains n integers x1,x2,…,xn (1≤xi≤109), where xi is the number that will fall on the dice in the i-th round.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output three integers a, l, and r such that Marian makes the most amount of money gambling with his strategy. If there are multiple answers, you may output any of them.

Example

input

4
5
4 4 3 4 4
5
11 1 11 1 11
1
1000000000
10
8 8 8 9 9 6 6 9 6 6

output

4 1 5
1 2 2
1000000000 1 1
6 6 10

Problem analysis

This question is about a game , One will appear randomly every time 1~10^9 Number of numbers , You can guess the number , Your gold coin can be doubled , On the contrary, halve , You know the future now n Number of rounds , Now you have only bought one number for a period of time , At first, there was only one gold coin , You should earn the most money during this period , Output the number of purchases and the start and end coordinates of this time period .

In fact, this question is similar dp The classic question of ： Maximum sub sum . We can enumerate one number at a time , The same number is regarded as 1, The rest are -1, Just find the sum of the largest sub segments , Record the largest sub segment and the interval in which it appears , And it's just the element of enumeration . But the normal way of writing is here n^2, no way , So we need to write in a different way .

We put all the same numbers into one vector in , And then to these vector Find the maximum sum of sub segments （ A little traversal process is omitted ）, these vector The total length of is n, The time complexity of finding the maximum sub segment sum is On.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int>v(n+1);
        map<int, vector<int>>mymap;
        for (int i = 1; i <= n; i++)
        {
            cin >> v[i];
            mymap[v[i]].push_back(i);
        }
        int res = 0, lx = -1, rx = -1, ans = -1;
        for (auto i : mymap)
        {
            int len = i.second.size();
            int x = 1, l = i.second[0], r = i.second[0];
            for (int j = 1; j < len; j++)
            {
                if (i.second[j] - l + 1 - (x + 1) < x + 1)
                {
                    x++;
                    r = i.second[j];
                    if (res < x-(r-l+1-x))
                    {
                        res = x-(r-l+1-x);
                        lx = l;
                        rx = r;
                        ans = i.first;
                    }
                }
                else
                {
                    if (res < x - (r - l + 1 - x))
                    {
                        res = x;
                        lx = l;
                        rx = r;
                        ans = i.first;
                        
                    }
                    l = i.second[j], r = i.second[j], x = 1;
                }
            }
            if (res < x - (r - l + 1 - x))
            {
                res = x-(r-l+1-x);
                lx = l;
                rx = r;
                ans = i.first;  
            }
        }
        cout << ans << " " << lx << " " << rx << endl;
    }
    return 0;
}