#include <iostream>

void shellsort(std::pair<int, int>* a, int leng);

int main()
{
	int n, i, j = 0;
	std::cout << "Enter size:" << std::endl;
	std::cin >> n;
	std::cout << "Enter elements:" << std::endl;
	std::pair<int, int>* mas = new std::pair<int, int>[n];
	for (i = 0; i < n; i++)
	{
		std::cin >> mas[i].first;
		mas[i].second = i;
	}
	shellsort(mas, n);
	for (int i = 0; i < n; ++i) {
		std::cout << mas[i].first << " ";
	}
	std::cout << std::endl;
	for (int i = 0; i < n; ++i) {
		std::cout << mas[i].second << " ";
	}
	std::cout << std::endl;
	std::cout << "min ind: " << mas[n - 1].second << std::endl;
	std::cout << "max ind: " << mas[0].second;
	delete[] mas;
}

void shellsort(std::pair<int, int>* a, int leng)
{
	int k = 0, i, j, p, step;
	std::pair<int, int> temp;
	int* gap = new int[leng];
	gap[0] = leng / 2;
	while (gap[k] > 1)
	{
		k++;
		gap[k] = gap[k - 1] / 2;
	}
	for (i = 0; i <= k; i++)
	{

		step = gap[i];
		for (j = step; j < leng; j++)
		{
			temp = a[j];
			p = j - step;
			while (p >= 0 && temp.first > a[p].first)
			{
				a[p + step] = a[p];
				p = p - step;
			}
			a[p + step] = temp;
		}
	}
}