Задача G. Арифметическая прогрессия ≡

Условие

Петя очень любит арифметические прогрессии. Однажды он написал на бумаге числовую последовательность, но, к сожалению, эта последовательность не оказалась арифметической прогрессией.

Чтобы исправить эту ситуацию, Петя решил вычеркнуть некоторые числа, чтобы полученная в результате вычёркивания последовательность оказалась арифметической прогрессией. При этом Петя хочет вычеркнуть как можно меньше чисел.

Напишите программу, принимающую на вход последовательность чисел и вычисляющую, какое наименьшее количество чисел нужно из неё вычеркнуть, чтобы оставшаяся последовательность оказалась арифметической прогрессией.

Формат входного файла

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

Примеры тестов

7
1 3 4 2 7 8 10

4
1 3 5 7

Разбор

Для решения задачи применим перебор плюс жадный алгоритм.

Требуется найти в данной последовательности чисел арифметическую прогрессию p₁, p₂, ..., p_M наибольшей длины. По определению арифметической прогрессии, p_i + 1 − p_i = d = const. Справедлива следующая формула для i-го члена прогрессии: p_i = p₁ + (i − 1)d. Таким образом, если известны p₁ и d, то арифметическая прогрессия определена однозначно.

Поскольку в задаче заранее неизвестно, какую конкретно арифметическую прогрессию нужно найти, напрашивается перебрать параметры p₁ и d. Для перебора p₁ будем перебирать индекс i первого члена прогрессии (a_i = p₁). Чтобы перебрать d, будем перебирать индекс j (j > i) второго члена прогрессии (a_j = p₂). Тогда d = p₂ − p₁ = a_j − a_i.

Теперь, когда мы перебрали i и j, нам известно, какую арифметическую прогрессию p₁, p₂, ..., p_M нужно искать в исходной последовательности. Местонахождения первого p₁ и второго p₂ членов прогрессии уже известны. Чтобы найти p₃, применим последовательный поиск среди чисел a_j + 1, a_j + 2, ..., a_M. Возможно два случая.

1. Среди этих чисел нет элемента, равного p₃. В этом случае прогрессии длины 3 с данными параметрами p₁ и d в исходной последовательности нет.
2. Среди этих чисел есть элемент, равный p₃.
   • Такой элемент ровно один. В этом случае местонахождение p₃ определено однозначно.
   • Таких элементов несколько. В этом случае нужно взять элемент с меньшим индексом (применяем жадный алгоритм).

Аналогичным образом ищем p₄, p₅ и т.д.