Дано множество натуральных чисел (все элементы множества попарно различны), упорядоченное по возрастанию значений. Интересным подмножеством исходного множества будем называть такое подмножество (возможно, полностью совпадающее с исходным множеством), что каждый его элемент больше мощности этого подмножества. Мощностью подмножества называется количество элементов в нем. Для данного множества необходимо найти размер наибольшего интересного подмножества, составленного из элементов этого множества.

Входные данные
Первая строка входных данных содержит целое число N — количество элементов исходного множества (1 ≤ N ≤ 105).

В следующих N строках записаны целые числа ai по одному в строке — элементы исходного множества (1 ≤ ai ≤ 2×109), упорядоченные по возрастанию значений.

Выходные данные
Программа должна вывести одно целое число — размер наибольшего интересного подмножества.

Система оценки
Решения, правильно работающие при N = 5, будут оцениваться в

Решения, правильно работающие при N ≤ 12, будут оцениваться в

Примеры
Ввод

Вывод

Пояснение

5
1
2
3
4
5

2

В множестве пять чисел: 1, 2, 3, 4, 5. В качестве интересного подмножества можно взять, например, подмножество {3, 5}. Его мощность равна 2 и все элементы этого подмножества больше 2. Интересного подмножества большего размера в данном примере не существует

#include <bits/stdc++.h>

using namespace std;

int main()

{

   int n;

   cin >> n;

   int a[n],b[n],mn = 100000, mx = 0, oko = 0,sum = 0;

   for(int i = 0; i < n; i++)

   {

       cin >> a[i];

       if(a[i] >= 0)

       {

           b[oko] = a[i];

           oko++;

       }

   }

   int index_of_minimum = 15, index_of_maximum = 0;

   for(int i = 0; i < oko; i++)

   {

       if(mn > b[i])

       {

           mn = min(mn,b[i]);

           index_of_minimum = min(index_of_minimum,i);

       }

       if(mx < b[i])

       {

           mx = max(mx,b[i]);

           index_of_maximum = i;

       }

   }

   for(int i = index_of_minimum; i < index_of_maximum + 1; i++)

   {

       sum += b[i];

   }

   mx = b[index_of_maximum - 1];

   mn = b[index_of_minimum];

   cout << sum << ' ' << mx * mn;

   return 0;

}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

   int s = 0, l = 1, n;

   cin >> n;

   vector <int> v(n);

   for (int i = 0; i < n; ++i)

   {

       cin >> v[i];

       if (v[i] > 0)

       {

           s += v[i];

       }

   }

   int imn = 0, imx = 0;

   for (int i = 0; i < n; ++i)

   {

       if (v[i] < v[imn])

       {

           imn = i;

       }

       if (v[i] > v[imx])

       {

           imx = i;

       }

   }

   if (imn > imx)

       {

           swap (v[imn], v[imx]);

       }

   for (int i = imn; i < imx; i++)

   {

       if (v[i] > 0)

       {

           l *= v[i];

       }

   }

   cout << s << " " << l;

   return 0;

}

Объяснение: