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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mitte (lewy+prawy)/2
#define debug //
using namespace std;
typedef long long ll;
typedef long double ld;
const ll g=1e16; //do tej wartosci wierze 2 duze liczby
//prefiksy beda mialy 10 cyfr
vector <ll> tab;
vector <int> rob;
int n;
ll res;
vector <int> pref;
void policz (ll a, vector <int> &rob)
{
	while (a>0)
	{
		rob.pb(a%10LL);
		a/=10LL;
	}
	reverse(rob.begin(), rob.end());
}
int main ()
{
	res=0;
	scanf ("%d", &n);
	tab.resize(n);
	rep(i,0,n) scanf ("%lld", &tab[i]);
	ll p=tab[0]; //poprzednia liczba
	int i;
	ll x, y;
	ll pot;
	ll dziel;
	bool f=true;
	ll z=0; //liczba zer poza prefiksem
	for (i=1; i<n; i++) 
	{
		
		if (p>g) 
		{
			debug ("nie male liczby!!!\n");
			f=false; //liczby juz nie sa male
		}
		
		
		x=tab[i];
		y=p;
		pot=1;
		res+=z; //one i tak musza to byc
		
		debug ("\nwynik to %d\n\n", res);
		debug ("robie liczbe %lld vs \n%lld (%d) \n", tab[i], p, z);
		
		while (y>0) //wyrownaj dlugosc - samego prefiksu
		{
			if (x==0) 
			{
				pot*=10LL;
				res++;
			}
			y/=10LL;
			x/=10LL;
		}
		
		debug ("dopelnil prefiks: \n%lld - %lld\n", tab[i]*pot, pot);
		
		if (tab[i]*pot>p) //nasz prefiks jest wiekszy
		{
			debug ("mam wiekszego prefiksa\n");
			p=tab[i]*pot;
			continue;
		}
		if (tab[i]<p/pot) //mamy mniejszy prefiks
		{
			debug ("mniejszy prefiks %lld vs %lld\n", tab[i], p/pot);
			if (f)
			{
				pot*=10LL;
				p=tab[i]*pot;
			}
			else 
			{
				z++;
				p=tab[i]*pot;
			}
			res++;
			continue; //problem rozwiazany
		}
		if (tab[i]==p/pot)
		{
			debug ("prefiksy rowne, moze moge dodac\n");
			if (f) //moge sprobowac dodac
			{
				p++;
				if (tab[i]==p/pot) continue; //wszystko dziala
				p--;
			}
			else
			{
				continue; //zawsze moge dodac do p i nikt sie nie kapnie
			}
			//nie moge dodac 1 - musze dopisac kolejna cyfre
			if (f)
			{
				pot*=10LL;
				p=tab[i]*pot;
			}
			else
			{
				z++;
				p=tab[i]*pot;
			}
			res++;
			continue;
		}
		debug ("przypadek nierozpatrzony!!\n");
	}
	printf ("%lld\n", res);
}