#include #define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<>_,_);_--;){ scanf("%d",&n); q=0; for(int i=1;i<=n;i++){ scanf("%d%d",&l[i],&r[i]); for(int j=-1;j<=1;j++){ C[++q]=l[i]+j; C[++q]=r[i]+j; } } sort(C+1,C+1+q); q=unique(C+1,C+1+q)-C-1; for(int i=1;i<=n;i++){ l[i]=lower_bound(C+1,C+1+q,l[i])-C; r[i]=lower_bound(C+1,C+1+q,r[i])-C; } for(int i=1;i<=q;i++) dp[i]=0; for(int i=1;i<=n;i++){ for(int j=2;j<=q;j++){ dp[j]=min(dp[j],dp[j-1]+(C[j]-C[j-1])*0.5); } for(int j=q-1;j>=1;j--){ dp[j]=min(dp[j],dp[j+1]+(C[j+1]-C[j])*0.5); } for(int j=1;j