#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;

const int N = 4e7;
int a[N];
int link[N];
int stack[N];
int ptr = 0;

void with_stack() {
	fill_n(link, N, -1);
	for (int i = 0; i < N; ++i) {
		while (ptr > 0 && a[stack[ptr - 1]] <= a[i]) {
			--ptr;
		}
		if (ptr) {
			link[i] = stack[ptr - 1];
		}
		stack[ptr++] = i;
	}
}

void without_stack() {
	for (int i = 0; i < N; ++i) {
		int &l = link[i];
		l = i - 1;
		while (l >= 0 && a[l] <= a[i]) {
			l = link[l];
		}
	}		
}

int main() {
	mt19937 randint;
	for (int i = 0; i < N; ++i) {
		a[i] = (int)randint();
	}
	
	long long start = clock();
	
	//with_stack();
	//without_stack();
	
	long long finish = clock();
	
	cout << 1000 * (finish - start) / CLOCKS_PER_SEC << " ms\n";
	
	return 0;
}