1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
int n,suma[2];
long long wynik;
string s;
vector<pii> v[2];
bool wieksze(vector<pii> &a, vector<pii> &b) {
	int p1=0,p2=0;
	while (p1<(int)a.size() && p2<(int)b.size()) {
		if (a[p1].first<b[p2].first) return false;
		if (a[p1].first>b[p2].first) return true;
		if (a[p1].second<b[p2].second) p1++;
		else {
			if (a[p1].second==b[p2].second) p1++;
			p2++;
		}
	}
	if (p1==(int)a.size()) return false;
	return true;
}
void wypisz(vector<pii>&a) {
	for (int x=0; x<(int)a.size(); x++) {
		int p=a[x].second;
		if (x>0) p-=a[x-1].second;
		while(p--)cout<<a[x].first;
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for (int i=0; i<n; i++) {
		int moj=i&1, pop=moj^1;
		cin>>s;
		v[moj].clear();
		for (int j=0; j<(int)s.length(); j++) v[moj].emplace_back(s[j]-'0',j+1);
		suma[moj]=s.length();
		if (i==0) continue;
		if (suma[moj]>suma[pop]) continue;
		if (wieksze(v[moj],v[pop])) {
			wynik+=suma[pop]-suma[moj];
			v[moj].emplace_back(0,suma[pop]);
			suma[moj]=suma[pop];
		} else {
			int poz=-1;
			for (int j=0,p1=0,p2=0; j<suma[moj]; ) {
				if (v[moj][p1].first<v[pop][p2].first) {
					poz=j;
					break;
				}
				if (v[moj][p1].second<v[pop][p2].second) j=v[moj][p1++].second;
				else {
					if (v[moj][p1].second==v[pop][p2].second) p1++;
					j=v[pop][p2++].second;
				}
			}
			if (poz!=-1) {
				wynik+=suma[pop]-suma[moj]+1;
				v[moj].emplace_back(0,suma[pop]+1);
				suma[moj]=suma[pop]+1;
			} else {
				for (int j=0; j<(int)v[pop].size(); j++) {
					if (v[pop][j].second>suma[moj] && v[pop][j].first<9) {
						poz=v[pop][j].second-1;
					}
				}
				if (poz==-1) {
					wynik+=suma[pop]-suma[moj]+1;
					v[moj].emplace_back(0,suma[pop]+1);
					suma[moj]=suma[pop]+1;
				} else {
					wynik+=suma[pop]-suma[moj];
					int x=0;
					while (v[pop][x].second<=suma[moj]) x++;
					while (v[pop][x].second<=poz) v[moj].push_back(v[pop][x++]);
					int pocz=x?v[pop][x-1].second:0;
					if (poz>pocz) v[moj].emplace_back(v[pop][x].first,poz);
					v[moj].emplace_back(v[pop][x].first+1,poz+1);
					if (poz+1<suma[pop]) v[moj].emplace_back(0,suma[pop]);
					suma[moj]=suma[pop];
				}
			}
		}
	}
	cout << wynik << endl;
}