AmShZ and G.O.A.T. (Codeforces 1610E)
Tags: Greedy, binary search

Let's call an array of $$$k$$$ integers $$$c_1, c_2, \ldots, c_k$$$ terrible, if the following condition holds:Let $$$AVG$$$ be the $$$\frac{c_1 + c_2 + \ldots + c_k}{k}$$$(the average of all the elements of the array, it doesn't have to be integer). Then the number of elements of the array which are bigger than $$$AVG$$$ should be strictly larger than the number of elements of the array which are smaller than $$$AVG$$$. Note that elements equal to $$$AVG$$$ don't count.For example $$$c = \{1, 4, 4, 5, 6\}$$$ is terrible because $$$AVG = 4.0$$$ and $$$5$$$-th and $$$4$$$-th elements are greater than $$$AVG$$$ and $$$1$$$-st element is smaller than $$$AVG$$$.Let's call an array of $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ bad, if at least one of its non-empty subsequences is terrible, and good otherwise.You are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Find the minimum number of elements that you have to delete from it to obtain a good array.An array is a subsequence of another array if it can be obtained from it by deletion of several (possibly, zero or all) elements.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the size of $$$a$$$.The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of array $$$a$$$.In each testcase for any $$$1 \le i \lt n$$$ it is guaranteed that $$$a_i \le a_{i+1}$$$.It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print the minimum number of elements that you have to delete from it to obtain a good array.

Note: In the first sample, the array $$$a$$$ is already good.In the second sample, it's enough to delete $$$1$$$, obtaining array $$$[4, 4, 5, 6]$$$, which is good.

Sample Inputs:
4
3
1 2 3
5
1 4 4 5 6
6
7 8 197860736 212611869 360417095 837913434
8
6 10 56026534 405137099 550504063 784959015 802926648 967281024

Sample Outputs:
0
1
2
3

Solution (Python):
from sys import stdin, stdout
t = int(stdin.readline())

def find_index(a, lower, upper):
    """"""
    ''
    target = a[lower] + a[upper]
    while upper - lower > 1:
        candidate = (upper + lower) // 2
        if 2 * a[candidate] > target:
            upper = candidate
        else:
            lower = candidate
    return lower
for _ in range(t):
    n = int(stdin.readline())
    a = [int(x) for x in stdin.readline().split()]
    answer = 0
    for lower in range(n - 1):
        temp = 1
        upper = n - 1
        while a[upper] > a[lower]:
            temp += 1
            upper = find_index(a, lower, upper)
        temp += upper - lower
        answer = max(answer, temp)
    stdout.write('{}\n'.format(n - answer))

Solution (Python):
import io
import os
from bisect import bisect_left
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve(a, n):
    ans = 0
    i = 0
    while i < n:
        cur = 1
        while i + 1 < n and a[i + 1] == a[i]:
            cur += 1
            i += 1
        lo = a[i]
        hi = a[i]
        j = i
        while True:
            j = bisect_left(a, hi + hi - lo, j + 1)
            if j >= n:
                break
            cur += 1
            hi = a[j]
        i += 1
        ans = max(ans, cur)
    return n - ans

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = [int(word) for word in input().strip().split()]
        print(solve(a, n))
if __name__ == '__main__':
    main()

Solution (Python):
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    ans = n
    for i in range(n):
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        index = i + 1
        temp = 1
        while index < n and arr[index] == arr[i]:
            index += 1
            temp += 1
        while index < n:
            temp += 1
            index = max(bisect.bisect_left(arr, 2 * arr[index] - arr[i]), index + 1)
        ans = min(ans, n - temp)
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1