Language: C++

#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>

class UnionFind {

public:
	using size_type = std::size_t;
	using container_type = std::vector<size_type>;

protected:
	container_type p, s;

public:
	UnionFind() : p(), s() {}
	explicit UnionFind(const size_type size)
		: p(size), s(size, static_cast<size_type>(1)) {
		std::iota(p.begin(), p.end(), static_cast<size_type>(0));
	}

	size_type size() const { return p.size(); }
	bool empty() const { return p.empty(); }

	size_type find(size_type x) {
		assert(x < size());
		while (p[x] != x)
			x = p[x] = p[p[x]];
		return x;
	}
	bool same(const size_type x, const size_type y) {
		assert(x < size());
		assert(y < size());
		return find(x) == find(y);
	}
	size_type size(const size_type x) {
		assert(x < size());
		return s[find(x)];
	}

	::std::pair<size_type,size_type> unite(size_type x, size_type y) {
		assert(x < size());
		assert(y < size());
		x = find(x);
		y = find(y);
		if (x != y) {
			if (s[x] < s[y])
				std::swap(x, y);
			s[x] += s[y];
			p[y] = x;
		}
		return{ x,y };
	}
};

#include <cassert>
#include <functional>
#include <utility>
#include <vector>

template <typename T, class Container = std::vector<T>,
	class Compare = std::less<typename Container::value_type>>
	class IntervalHeap {

	public:
		using container_type = Container;
		using value_compare = Compare;
		using value_type = typename container_type::value_type;
		using reference = typename container_type::reference;
		using const_reference = typename container_type::const_reference;
		using size_type = typename container_type::size_type;

	protected:
		container_type c;
		value_compare comp;

	private:
		static constexpr size_type z = ~static_cast<size_type>(1);
		bool normalize(const size_type x, const size_type y) {
			if (!comp(c[y], c[x]))
				return false;
			std::swap(c[x], c[y]);
			return true;
		}
		void build() {
			const size_type s = size() + 1;
			if (s & 1) {
				normalize(s & z, s);
				buildmin(s >> 1);
				buildmax(s >> 1);
				return;
			}
			if (s == 2)
				return;
			if (normalize(s, s >> 1 | 1))
				buildmax(s >> 2);
			buildmin(s >> 1);
		}
		void buildmin(size_type i) {
			while (i > 1 && normalize(i & z, i << 1))
				i >>= 1;
		}
		void buildmax(size_type i) {
			while (i > 1 && normalize(i << 1 | 1, i | 1))
				i >>= 1;
		}

	public:
		explicit IntervalHeap(const value_compare &x = value_compare())
			: c(2), comp(x) {}
		bool empty() const { return c.size() == 2; }
		size_type size() const { return c.size() - 2; }
		const_reference min() const {
			assert(!empty());
			return c[2];
		}
		const_reference max() const {
			assert(!empty());
			return size() == 1 ? c[2] : c[3];
		}
		void push(const value_type &x) {
			c.push_back(x);
			build();
		}
		void push(value_type &&x) {
			c.push_back(std::move(x));
			build();
		}
		template <class... Args> void emplace(Args &&... args) {
			c.emplace_back(std::forward<Args>(args)...);
			build();
		}
		void pop_min() {
			assert(!empty());
			const size_type s = size() + 1;
			std::swap(c[2], c[s]);
			c.pop_back();
			size_type i = 4;
			while (i < s) {
				if ((i | 2) < s && !comp(c[i], c[i | 2]))
					i |= 2;
				if (!normalize(i >> 1 & z, i))
					return;
				if ((i | 1) < s)
					normalize(i, i | 1);
				i <<= 1;
			}
		}
		void pop_max() {
			assert(!empty());
			const size_type s = size() + 1;
			if (s == 2)
				return pop_min();
			std::swap(c[3], c[s]);
			c.pop_back();
			size_type i = 5;
			while (i < s) {
				if ((i | 2) < s && !comp(c[i | 2], c[i]))
					i |= 2;
				if (!normalize(i, i >> 1 | 1))
					return;
				normalize(i & z, i);
				i = (i & z) << 1 | 1;
			}
		}
};

#include <cassert>
#include <cstddef>
#include <functional>
#include <memory>
#include <type_traits>
#include <utility>

template <class TotallyOrderedSet> class pairing_heap {

public:
	using set_type = TotallyOrderedSet;
	using value_type = typename set_type::value_type;
	using const_reference = const value_type &;
	using size_type = std::size_t;

private:
	struct node_t {
		value_type value;
		std::unique_ptr<node_t> left, right;
		template <class... Args>
		node_t(Args &&... args) noexcept(
			std::is_nothrow_constructible<value_type, Args...>::value)
			: value(std::forward<Args>(args)...), left(), right() {}
	};
	using pointer = std::unique_ptr<node_t>;
	pointer root;
	size_type s;
	static pointer merge(pointer x, pointer y) noexcept(
		noexcept(set_type::less_equal(std::declval<value_type>(),
			std::declval<value_type>()))) {
		if (!set_type::less_equal(x->value, y->value))
			x.swap(y);
		y->right = std::move(x->left);
		x->left = std::move(y);
		return std::move(x);
	}
	static pointer mergelist(pointer curr) noexcept(
		noexcept(merge(std::declval<pointer>(), std::declval<pointer>()))) {
		pointer head, temp, next;
		while (curr) {
			next = std::move(curr->right);
			if (next) {
				temp = std::move(next->right);
				curr = merge(std::move(curr), std::move(next));
			}
			curr->right = std::move(head);
			head = std::move(curr);
			curr = std::move(temp);
		}
		if (head) {
			curr = std::move(head);
			head = std::move(curr->right);
		}
		while (head) {
			next = std::move(head->right);
			curr = merge(std::move(curr), std::move(head));
			head = std::move(next);
		}
		return std::move(curr);
	}

public:
	pairing_heap() noexcept : root(), s(0) {}

	bool empty() const noexcept { return !root; }
	size_type size() const noexcept { return s; }

	const_reference top() const noexcept {
		assert(!empty());
		return root->value;
	}

	void push(const value_type &x) {
		if (empty())
			root = std::make_unique<node_t>(x);
		else
			root = merge(std::move(root), std::make_unique<node_t>(x));
		++s;
	}
	void push(value_type &&x) {
		if (empty())
			root = std::make_unique<node_t>(std::move(x));
		else
			root = merge(std::move(root), std::make_unique<node_t>(std::move(x)));
		++s;
	}
	template <class... Args> void emplace(Args &&... args) {
		if (empty())
			root = std::make_unique<node_t>(std::forward<Args>(args)...);
		else
			root = merge(std::move(root),
				std::make_unique<node_t>(std::forward<Args>(args)...));
		++s;
	}

	void pop() noexcept(noexcept(mergelist(std::declval<pointer>()))) {
		assert(!empty());
		root = mergelist(std::move(root->left));
		--s;
	}

	pairing_heap &meld(pairing_heap &other) noexcept(
		noexcept(merge(std::declval<pointer>(), std::declval<pointer>()))) {
		if (!other.empty()) {
			s += other.s;
			other.s = 0;
			root = merge(std::move(root), std::move(other.root));
		}
		return *this;
	}
	pairing_heap &operator+=(pairing_heap &other) noexcept(
		noexcept(meld(std::declval<pairing_heap>()))) {
		return meld(other);
	}
};

#include <algorithm>
#include <limits>
#include <utility>

template <class T> class ordered_set {
public:
	using value_type = T;

	static bool less_equal(const value_type &x, const value_type &y) noexcept(
		noexcept(std::declval<value_type>() <= std::declval<value_type>())) {
		return x <= y;
	}
};

#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <tuple>
#include <vector>

int main() {
	int n, k, q;
	::std::cin >> n >> k >> q;
	::std::vector<int> a(n), b(n);
	for (auto &e : a)
		::std::cin >> e;
	::std::iota(b.begin(), b.end(), 0);
	::std::sort(b.begin(), b.end(), [&](int x, int y) {return a[x] > a[y];});

	::std::vector<char> used(n, 0);
	UnionFind T(n);
	IntervalHeap<int> H;
	::std::vector<pairing_heap<ordered_set<int>>> heaps(n);
	int ans = ::std::numeric_limits<int>::max();
	for (int i = 0;i < n;++i)
		heaps[i].emplace(a[i]);
	for (const auto i : b) {
		used[i] = 1;
		if (i != 0 && used[i - 1]) {
			int x, y;
			::std::tie(x, y) = T.unite(i, i - 1);
			heaps[x] += heaps[y];
		}
		if (i != n - 1 && used[i + 1]) {
			int x, y;
			::std::tie(x, y) = T.unite(i, i + 1);
			heaps[x] += heaps[y];
		}
		auto &t = heaps[T.find(i)];
		while (t.size() >= k) {
			H.emplace(t.top());
			t.pop();
		}
		if (H.size() >= q) {
			while (H.size() > q)
				H.pop_max();
			ans = ::std::min(ans, H.max() - H.min());
		}
	}

	::std::cout << ans << ::std::endl;

	return 0;
}

Compiler output:
a.cc: In instantiation of 'pairing_heap<TotallyOrderedSet>& pairing_heap<TotallyOrderedSet>::operator+=(pairing_heap<TotallyOrderedSet>&) [with TotallyOrderedSet = ordered_set<int>]':
a.cc:327:23:   required from here
  327 |                         heaps[x] += heaps[y];
      |                                            ^
a.cc:280:30: error: cannot bind non-const lvalue reference of type 'pairing_heap<ordered_set<int> >&' to an rvalue of type 'pairing_heap<ordered_set<int> >'
  280 |                 noexcept(meld(std::declval<pairing_heap>()))) {
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:270:42: note:   initializing argument 1 of 'pairing_heap<TotallyOrderedSet>& pairing_heap<TotallyOrderedSet>::meld(pairing_heap<TotallyOrderedSet>&) [with TotallyOrderedSet = ordered_set<int>]'
  270 |         pairing_heap &meld(pairing_heap &other) noexcept(
      |                            ~~~~~~~~~~~~~~^~~~~