[Solution] Gambling Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Gambling Codeforces Solution | Codeforces Problem Solution 2022

H. Gambling

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Before each round, the player selects a number between 1$1$ and 109${10}^9$. After that, a dice with 109${10}^9$ faces is rolled so that a random number between 1$1$ and 109${10}^9$ 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$x_1,x_2,\dots ,x_n$ that the dice will show in the next n$n$ rounds.

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

Solution Click Below:-  CLICK HERE

Marian asks you to determine the integers a$a$, l$l$ and r$r$ (1≤a≤109$1\le a\le {10}^9$, 1≤l≤r≤n$1\le l\le r\le 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 11024${\displaystyle \frac{1}{1024}}$, 1128${\displaystyle \frac{1}{128}}$, 12${\displaystyle \frac{1}{2}}$, 1$1$, 2$2$, 4$4$, etc. (any value of 2t$2^t$, where t$t$ is an integer of any sign).

Input

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

Marathon Codeforces Solution

Gambling Codeforces Solution

All Distinct Codeforces Solution

Where's the Bishop? Codeforces Solution

The Clock Codeforces Solution

Binary Deque Codeforces Solution

3SUM Codeforces Solution

2^Sort Codeforces Solution

Gambling Codeforces Solution

The first line of each test case contains a single integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$) — the number of rounds.

The second line of each test case contains n$n$ integers x1,x2,…,xn$x_1,x_2,\dots ,x_n$ (1≤xi≤109$1\le x_i\le {10}^9$), where xi$x_i$ is the number that will fall on the dice in the i$i$-th round.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output three integers a$a$, l$l$, and r$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.